Napisz program lub funkcję do wyjścia sumę liczb nieparzystych kwadratowych (OEIS # A016754) mniej niż wejście n .

Pierwsze 44 liczby w sekwencji to:

1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089, 
1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481, 
3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625, 5929, 6241, 6561, 6889, 7225, 7569

Wzór na sekwencję to a(n) = ( 2n + 1 ) ^ 2.

Notatki

• Zachowanie programu może być niezdefiniowane n < 1(tzn. Wszystkie prawidłowe dane wejściowe są >= 1.)

Przypadki testowe

1 => 0
2 => 1
9 => 1
10 => 10
9801 => 156849
9802 => 166650
10000 => 166650

Galaretka, 6 bajtów

½Ċ|1c3

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

Dla wszystkich dodatnich liczb całkowitych k mamy 1² + 3² + ⋯ + (2k - 1) ² = k (2k - 1) (2k +1) ÷ 3 .

Ponieważ są m C r = m! ÷ ((mr)! R!) R - kombinacje zbioru m elementów, powyższe można obliczyć jako (2k + 1) C 3 = (2k + 1) 2k (2k - 1) ÷ 6 = k (2k - 1) (2k + 1) ÷ 3.

Aby zastosować formułę, musimy znaleźć najwyższe 2k + 1 takie, że (2k - 1) ² <n . Ignorując przez chwilę parzystość, możemy obliczyć najwyższą m taką, że (m - 1) ² <n jako m = ceil (srqt (n)) . Aby warunkowo zwiększyć wartość m, jeśli jest równa, wystarczy obliczyć wartość m | 1 (bitowe LUB z 1 ).

Jak to działa

½Ċ|1c3  Main link. Argument: n

½       Compute the square root of n.
 Ċ      Round it up to the nearest integer.
  |1    Bitwise OR with 1 to get an odd number.
    c3  Compute (2k + 1) C 3 (combinations).

JavaScript (ES6), 30 bajtów

f=(n,i=1)=>n>i*i&&i*i+f(n,i+2)

31 bajtów, jeśli f(1)trzeba zwrócić zero zamiast false:

f=(n,i=1)=>n>i*i?i*i+f(n,i+2):0

05AB1E , 10 8 bajtów

Kod:

<tLDÉÏnO

Wyjaśnienie:

<         # Decrease by 1, giving a non-inclusive range.
 t        # Take the square root of the implicit input.
  L       # Generate a list from [1 ... sqrt(input - 1)].
   DÉÏ    # Keep the uneven integers of the list.
      n   # Square them all.
       O  # Take the sum of the list and print implicitly.

Może się przydać: t;L·<nO.

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Haskell, 30 bajtów

f n=sum[x^2|x<-[1,3..n],x^2<n]

Zaskakująco normalnie wyglądający.

C #, 126 131 bajtów

Zmodyfikowana wersja zgodna z nowym pytaniem:

class P{static void Main(){int x,s=0,n=int.Parse(System.Console.ReadLine());for(x=1;x*x<n;x+=2)s+=x*x;System.Console.Write(s);}}

Korzystanie z ustalonego limitu:

using System;namespace F{class P{static void Main(){int x,s=0;for(x=1;x<100;x+=2)s+=x*x;Console.Write(s);Console.Read();}}}

Galaretka, 7

’½R²m2S

Wypróbuj online lub wypróbuj zmodyfikowaną wersję dla wielu wartości

Ćśś ... Dennis śpi ...

Dzięki Sp3000 na czacie za pomoc!

Wyjaśnienie:

’½R²m2S
’           ##  Decrement to prevent off-by-one errors
 ½R²        ##  Square root, then floor and make a 1-indexed range, then square each value
    m2      ##  Take every other value, starting with the first
      S     ##  sum the result

R, 38 36 bajtów

function(n,x=(2*0:n+1)^2)sum(x[x<n])

@Giuseppe zapisał dwa bajty, przechodząc xdo listy argumentów, aby zapisać nawiasy klamrowe. Fajny pomysł!

Nie golfił

function(n, x = (2*(0:n) + 1)^2)  # enough odd squares (actually too many)
  sum(x[x < n])                   # subset on those small enough
}

Wypróbuj online!

C, 51, 50 48 bajtów

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}

Bo dlaczego nie golf w jednym z najbardziej pełnych języków? (Hej, przynajmniej nie jest to Java!)

Wypróbuj online!

Pełny program bez golfa, z testowym wejściem / wyjściem:

int main()
{
    int s;
    f(10, &s);
    printf("%d\n", s);
    char *foobar[1];
    gets(foobar);
}

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}

Właściwie 7 bajtów

√K1|3@█

Wypróbuj online!

Również dla 7 bajtów:

3,√K1|█

Wypróbuj online!

Wykorzystuje to tę samą formułę, co w odpowiedzi Jelly'ego na Jelly.

Wyjaśnienie:

√K1|3@█
√K       push ceil(sqrt(n))
  1|     bitwise-OR with 1
    3@█  x C 3

Oktawa, 23 bajty

@(x)(x=1:2:(x-1)^.5)*x'

Testowanie:

[f(1); f(2); f(3); f(10); f(9801); f(9802); f(10000)]
ans =    
        0
        1
        1
       10
   156849
   166650
   166650

CJam, 15 bajtów

qi(mq,2%:)2f#1b

Wypróbuj online!

Zakodowane 10000 rozwiązań:

12 bajtowe rozwiązanie Martina:

99,2%:)2f#1b

Moje oryginalne 13-bajtowe rozwiązanie:

50,{2*)2#}%:+

Wypróbuj online!

Pyth, 10 bajtów

s<#Qm^hyd2

Zestaw testowy

Wyjaśnienie:

s<#Qm^hyd2
    m          Map over the range of input (0 ... input - 1)
       yd      Double the number
      h        Add 1
     ^   2     Square it
 <#            Filter the resulting list on being less than
   Q           The input
s              Add up what's left

Mathcad, 31 „bajtów”

Zauważ, że Mathcad używa skrótów klawiaturowych do wprowadzania kilku operatorów, w tym definicji i wszystkich operatorów programowania. Na przykład ctl-] wchodzi w pętlę while - nie można jej wpisać i można ją wprowadzić tylko za pomocą skrótu klawiaturowego lub z paska narzędzi Programowanie. „Bajty” to liczba operacji na klawiaturze potrzebnych do wprowadzenia elementu Mathcad (np. Nazwa zmiennej lub operator).

Ponieważ nie mam szans na wygraną w tym konkursie, pomyślałem, że dodam trochę urozmaicenia dzięki bezpośredniej wersji formuły.

Rakieta, 57 bajtów

(λ(n)(for/sum([m(map sqr(range 1 n 2))]#:when(< m n))m))

MATL , 10 bajtów

qX^:9L)2^s

EDYCJA (30 lipca 2016 r.): Połączony kod zastępuje się 9Lprzez, 1Laby dostosować się do ostatnich zmian w języku.

Wypróbuj online!

q    % Implicit input. Subtract 1
X^   % Square root
:    % Inclusive range from 1 to that
9L)  % Keep odd-indexed values only
2^   % Square
s    % Sum of array

Python, 39 bajtów

f=lambda n,i=1:+(i*i<n)and i*i+f(n,i+2)

Jeśli, na n=1, to ważny do wyjścia Falsezamiast 0, to możemy uniknąć konwersji przypadku bazowego, aby uzyskać 37 bajtów

f=lambda n,i=1:i*i<n and i*i+f(n,i+2)

To dziwne, że nie znalazłem krótszą drogę do zdobycia 0dla i*i>=ni niezerowe inaczej. W Pythonie 2 wciąż dostaje się 39 bajtów

f=lambda n,i=1:~-n/i/i and i*i+f(n,i+2)

Python, 42 38 bajtów

f=lambda n,i=1:i*i<n and i*i+f(n,i+2)

Python 2, 38 bajtów

s=(1-input()**.5)//2*2;print(s-s**3)/6

Na podstawie wzoru Dennisa , z s==-2*k. Wysyła liczbę zmiennoprzecinkową. W efekcie dane wejściowe są pierwiastkowane, zmniejszane, a następnie zaokrąglane w górę do następnej liczby parzystej.

PARI / GP , 33 32 26 bajtów

Zaadaptowano z kodu Dennisa :

n->t=(1-n^.5)\2*2;(t-t^3)/6

Mój pierwszy pomysł (30 bajtów), używając prostej formuły wielomianowej:

n->t=((n-1)^.5+1)\2;(4*t^3-t)/3

Jest to wydajna implementacja, właściwie nie bardzo różna od wersji bez golfisty, którą napisałbym:

a(n)=
{
  my(t=ceil(sqrtint(n-1)/2));
  t*(4*t^2-1)/3;
}

Alternatywna implementacja (37 bajtów), która zapętla się nad każdym z kwadratów:

n->s=0;t=1;while(t^2<n,s+=t^2;t+=2);s

Inne alternatywne rozwiązanie (35 bajtów) demonstrujące sumowanie bez zmiennej tymczasowej:

n->sum(k=1,((n-1)^.5+1)\2,(2*k-1)^2)

Jeszcze inne rozwiązanie, niezbyt konkurencyjne (40 bajtów), wykorzystujące normę L ² . Byłoby lepiej, gdyby istniało wsparcie dla wektorów ze wskaźnikami wielkości kroku. (Można sobie wyobrazić składnię, n->norml2([1..((n-1)^.5+1)\2..2])która zrzuci 8 bajtów).

n->norml2(vector(((n-1)^.5+1)\2,k,2*k-1))

Haskell, 32 31 bajtów

 n#x=sum[x^2+n#(x+2)|x^2<n]
 (#1)

Przykład użycia: (#1) 9802-> 166650.

Edycja: @xnor zapisał bajt ze sprytnym zrozumieniem listy. Dzięki!

Julia, 29 bajtów

f(n,i=1)=i^2<n?i^2+f(n,i+2):0

Jest to funkcja rekurencyjna, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą.

Indeks rozpoczynamy od 1, a jeśli jego kwadrat jest mniejszy niż wartość wejściowa, bierzemy kwadrat i dodajemy wynik ponownego użycia do indeksu + 2, co zapewnia pomijanie liczb parzystych, w przeciwnym razie zwracamy 0.

Oracle SQL 11.2, 97 bajtów

SELECT NVL(SUM(v),0)FROM(SELECT POWER((LEVEL-1)*2+1,2)v FROM DUAL CONNECT BY LEVEL<:1)WHERE v<:1;

Julia, 26 bajtów

x->sum((r=1:2:x-1)∩r.^2)

To konstruuje zakres wszystkich nieparzystych, dodatnich liczb całkowitych poniżej n i tablicę kwadratów liczb całkowitych w tym zakresie, a następnie oblicza sumę liczb całkowitych w obu iterowalnych.

Wypróbuj online!

Reng v.3.3, 36 bajtów

0#ci#m1ø>$a+¡n~
:m%:1,eq^c2*1+²c1+#c

Wypróbuj tutaj!

Wyjaśnienie

1: inicjalizacja

 0#ci#m1ø

Ustawia cna 0(licznik) i dane wejściowe Ido msiekiery. 1øprzechodzi do następnej linii.

2: pętla

:m%:1,eq^c2*1+²c1+#c

:powiela bieżącą wartość (kwadratową liczbę nieparzystą) i [I mkładzie msiekierę w dół. Użyłem mniej niż lewy w innej odpowiedzi , której tu używam. %:1,esprawdza, czy STOS <TOS. Jeśli tak, q^idzie w górę i wychodzi z pętli. Inaczej:

         c2*1+²c1+#c

codkłada licznik, 2*podwaja go, 1+dodaje jeden i podnosi ²go do kwadratu. c1+#Czwiększa się c, a pętla znów się uruchamia.

3: końcowy

        >$a+¡n~

$upuszcza ostatnią wartość (większą niż pożądana), a+¡dodaje, aż długość stosu wynosi 1, n~wysyła i kończy.

Clojure, 53 bajty

#(reduce +(map(fn[x](* x x))(range 1(Math/sqrt %)2)))

Możesz to sprawdzić tutaj:  https://ideone.com/WKS4DA

Mathematica 30 bajtów

Total[Range[1,Sqrt[#-1],2]^2]&

Ta nienazwana funkcja Range[1,Sqrt[#-1],2]podnosi do kwadratu wszystkie liczby nieparzyste mniejsze niż input ( ) i dodaje je.

PHP, 64 bajty

function f($i){$a=0;for($k=-1;($k+=2)*$k<$i;$a+=$k*$k);echo $a;}

Rozszerzony:

function f($i){
    $a=0;
    for($k=-1; ($k+=2)*$k<$i; $a+=$k*$k);
    echo $a;
}

Na każdej iteracji forpętli, doda 2 k i sprawdzić czy k ² jest mniejsza niż $i, jeśli jest to dodatek k ² do $a.

R, 60 bajtów

function(n){i=s=0;while((2*i+1)^2<n){s=s+(2*i+1)^2;i=i+1};s}

Robi dokładnie tak, jak opisano w pytaniu, w tym zwraca 0 dla przypadku n = 1. Degolfed, ”;” reprezentuje podział linii w R, zignorowany poniżej:

function(n){         # Take input n
i = s = 0            # Declare integer and sum variables
while((2*i+1)^2 < n) # While the odd square is less than n
s = s + (2*i+1)^2    # Increase sum by odd square
i = i + 1            # Increase i by 1
s}                   # Return sum, end function expression

Java 8, 128 119 117 111 49 bajtów

n->{int s=0,i=1;for(;i*i<n;i+=2)s+=i*i;return s;}

Na podstawie rozwiązania C # @Thomas .

Wyjaśnienie:

Wypróbuj online.

n->{           // Method with integer as both parameter and return-type
  int s=0,     //  Sum, starting at 0
      i=1;     //  Index-integer, starting at 1
  for(;i*i<n;  //  Loop as long as the square of `i` is smaller than the input
      i+=2)    //    After every iteration, increase `i` by 2
    s+=i*i;    //   Increase the sum by the square of `i`
  return s;}   //  Return the result-sum

Python 2, 49 bajtów

To skończyło się na krótszym niż a lambda.

x=input()
i=1;k=0
while i*i<x:k+=i*i;i+=2
print k

Wypróbuj online

Moi najkrótsze lambda, 53 bajtów :

lambda x:sum((n-~n)**2for n in range(x)if(n-~n)**2<x)