Policz sumy dwóch kwadratów

45

Biorąc pod uwagę liczbę nieujemną n, wypisz liczbę sposobów wyrażenia njako sumę dwóch kwadratów liczb całkowitych n == a^2 + b^2( OEIS A004018 ). Zauważ, że ai bmogą być dodatnie, ujemne lub zero, a ich kolejność ma znaczenie. Wygrywa najmniej bajtów.

Na przykład n=25daje, 12ponieważ 25można wyrazić jako

(5)^2  + (0)^2
(4)^2  + (3)^2
(3)^2  + (4)^2
(0)^2  + (5)^2
(-3)^2 + (4)^2
(-4)^2 + (3)^2
(-5)^2 + (0)^2
(-4)^2 + (-3)^2
(-3)^2 + (-4)^2
(0)^2  + (-5)^2
(3)^2  + (-4)^2
(4)^2  + (-3)^2

Oto wartości do n=25. Uważaj, aby Twój kod działał n=0.

0 1
1 4
2 4
3 0
4 4
5 8
6 0
7 0
8 4
9 4
10 8
11 0
12 0
13 8
14 0
15 0
16 4
17 8
18 4
19 0
20 8
21 0
22 0
23 0
24 0
25 12

Oto wartości do n=100listy.

[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12]

Zabawne fakty: Sekwencja zawiera terminy, które są dowolnie wysokie, a limit jej średniej ruchomej wynosi π.

Tabela liderów:

xnor
źródło
4
Czekaj, co?? „Sekwencja zawiera terminy, które są dowolnie wysokie, a limit jej średniej ruchomej wynosi π.”
Stewie Griffin
@StewieGriffin Oba stwierdzenia są spójne. Rozważ sekwencję 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Odcinając sekwencję po dowolnej niezerowej liczbie, średnia jak dotąd wynosi 1. I biegi zer mają coraz mniejszy wpływ na później w sekwencji.
xnor
5
Wiem, że jest spójny .. =) Sprawdziłem 10 000 pierwszych liczb, kiedy opublikowałem komentarz. Nie rozumiem: dlaczego, u licha, jest równe Pi?
Stewie Griffin
29
@StewieGriffin Suma terminów do N odpowiada punktom (a, b) z ^ 2 + b ^ 2 <= N. Są to punkty sieci w okręgu o promieniu sqrt (N), którego powierzchnia wynosi πN.
xnor
2
@xnor i tam idzie magia :(
Andras Deak

Odpowiedzi:

19

Python ( 59 57 56 bajtów)

lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

Demo online

Podobnie jak w przypadku mojej odpowiedzi CJam, wykorzystuje to inwersję Möbiusa i działa w czasie pseudo-kwazilinearnym.

Dzięki Sp3000 za 2 bajty oszczędności i feersum za 1.

Peter Taylor
źródło
1
Te nawiasy są denerwujące.
lirtosiast
@ThomasKwa, powiedz mi o tym. Rzeczą, która naprawdę mnie zaskoczyła, w jednej z wersji, które przeszedłem do pierwszej, którą opublikowałem, było -1**xto, że zawsze -1. Spodziewałem się, że -1będzie to pojedynczy dosłowny całkowity token, a nie jednorzędny minus o niskim priorytecie, po którym następuje jeden.
Peter Taylor
2
Gratulujemy nagrody! Twój kod jest krótszy niż cokolwiek, co wymyśliłem. Twoje rozwiązanie opiera się na zupełnie nowej i nieoczekiwanej matematycznej idei i sprawia mi radość, że jest to możliwe nawet przy tak prosto wyglądającym wyzwaniu. Odwrotny wynik Mobiusa jest całkiem ładny i czerpałem przyjemność z czerpania dowodów na siebie.
xnor
1 bajt można zapisać, przenosząc mnożenie przez 4 na później **x.
feersum,
@PeterTaylor Czy możesz wyjaśnić, jak działa Twój algorytm / czy możesz wskazać mi zasób? Nie do końca rozumiem, jak zastosować odwrócenie Möbiusa do liczby problemów sumarycznych.
flawr
15

Mathematica, 13 bajtów

Jeśli dozwolone są wbudowane, tak to zrobić w Mathematica.

2~SquaresR~#&

Dla 0 <= n <= 100

2~SquaresR~# & /@ Range[0, 100]

{1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0 , 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4 , 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8 , 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0 , 12}

DavidC
źródło
1
Ponieważ Mathematica ma do tego wbudowaną funkcję.
HyperNeutrino,
14

Python 2, 44 bajty

f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2

Jest to prawie to samo co rozwiązanie xsot (oparte na rozwiązaniu Petera Taylora ), ale oszczędza 8 bajtów, upraszczając sposób obsługi znaków.

Pamiętaj, że w przypadku pełnego programu możemy zapisać 2 bajty w funkcji bez ponoszenia kosztów poza funkcją:

f=lambda n,x=1:x>n or(n%x<1)-f(n,x+2)/4<<2
print+f(input())

Dwa dodatkowe bajty dla pełnego programu w ten sposób:

n=input()
f=lambda x:x>n or(n%x<1)-f(x+2)/4<<2
print+f(1)

Dla n > 0tam jest bardzo czytelne rozwiązanie 40-bajtowy:

f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)
Mitch Schwartz
źródło
1
Gratulacje za wygraną! Odejmowanie rekurencyjne jest czystą i krótką drogą do wyrażenia naprzemiennej sumy dla nieparzystych dzielników bez konieczności wydobywania znaku z samego dzielnika. Podziękowania dla xsot za usprawnienie rozwiązania Petera Taylora do rekurencyjnego z sprytną obsługą n = 0.
xnor
12

Pyth, 13 bajtów

/sM^^R2}_QQ2Q

Zestaw testowy

/sM^^R2}_QQ2Q
                 Q = eval(input())
       }_QQ      Inclusive range from -Q to Q (all possible a and b)
    ^R2          Map to their squares
   ^       2     Form all pairs
 sM              Sum pairs
/           Q    Count occurances of Q
isaacg
źródło
Późno, ale nie sądzę, żebyś potrzebował ostatniego Q.
Erik the Outgolfer,
12

J, 16 bajtów

+/@,@:=+&*:/~@i:

Jest to czasownik monadyczny (innymi słowy, jednoargumentowa funkcja). Wypróbuj online lub sprawdź, czy pomyślnie przeszedł wszystkie przypadki testowe .

Wyjaśnienie

+/@,@:=+&*:/~@i:  Denote input by n
              i:  The array of integers from -n to n
           /~@    Take outer product wrt the following function:
       +           the sum of
        &*:        squares of both inputs
                  This results in a 2D array of a^2+b^2 for all a, b between -n and n
      =           Replace by 1 those entries that are equal to n, and others by 0
   ,@:            Flatten the binary matrix
+/@               Take its sum
Zgarb
źródło
11

Python 2, 69 55 53 52 bajty

f=lambda n,x=1:+(x>n)or(2-x%4)*(n%x<1)+f(n,x+2)/4<<2

Jest to funkcja rekurencyjna oparta na doskonałym rozwiązaniu Petera Taylora .

xsot
źródło
1
To świetna poprawa. Ale wciąż istnieje sposób, aby go skrócić i zachęcam do szukania go.
xnor
1
@xnor Kolejny bajt w dół. Mam nadzieję, że nie masz już żadnych sztuczek w rękawach.
xsot,
2
Nie wiem, czy powinienem złożyć odpowiedzi na nią, to tylko rozwiązanie plus jeden trick: f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2. Sądzę też, że nie obchodzi nas przekroczenie domyślnej maksymalnej głębokości rekurencji?
Mitch Schwartz,
1
@MitchSchwartz Myślę, że to niesamowita poprawa warta nagrody i prawdopodobnie ostateczna optymalizacja xnor miała na myśli.
xsot,
1
@MitchSchwartz Tak, to była optymalizacja, o której myślałem! A /4<<2sztuczka xsot czyni go krótszym niż to, co miałem.
xnor
8

Julia, 40 bajtów

n->n>0?4sum(i->(n-i^2)^.5%1==0,1:n^.5):1

Nie golfowany:

function f(n)
  if n==0
    return 1           # Handle special case of n=0
  else
    m=0                # Start the counter at zero
    for i=1:sqrt(n)    # Loop over the values (i) whose squares are
                       # less than n (except zero)
      k=sqrt(n-i^2)    # Find k such that n=k^2+i^2
      if k==floor(k)   # if k is an integer, we've found a pair
        m+=4           # Add one for each of k^2+i^2, (-k)^2+(-i)^2, and the other two
      end
    end
    return m           # Return the resulting count
  end
end

Zauważ, że pętla nie obejmuje i==0, ponieważ gdy njest kwadratem, jest już uwzględniona przez i=sqrt(n), i są tylko cztery, a nie osiem, dla tej formy ( 0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2).

Glen O
źródło
7

CJam, 25 23 bajtów

Zri:R#Ym*{Rf-Yf#:+R=},,

Jest to rozwiązanie teoretyczne, które wymaga O (9 n ) czasu i pamięci na wejście n .

Kosztem jednego dodatkowego bajtu - w sumie 24 bajtów - możemy zredukować złożoność do O (n 2 ) :

ri:R)Y*Ym*{Rf-Yf#:+R=},,

Wypróbuj online!

Jak to działa

Zarówno

Z                  Push 3.
 ri:R              Read an integer from STDIN and save it in R.
     #             Compute 3**R.

lub

ri:R               Read an integer from STDIN and save it in R.
    )Y*            Add 1 and multiply by 2.

Następnie

Ym*                Take the second Cartesian power, i.e., compute all pairs.
   {          },   Filter the pairs:
    Rf-              Subtract R from each.
       Yf#           Square the differences.
          :+         Add the squares.
            R=       Compare with R.
                   If = pushed 1, keep the pair.
                ,  Count the kept pairs.
Dennis
źródło
Zaoszczędzając jeden bajt można zmniejszyć złożoność do Õ (n)
Peter Taylor
Tak widziałem. To wspaniale.
Dennis
7

CJam ( 25 24 22 21 bajtów)

{:X!X{X\2*)%!4*\-}/z}

Demo online

Działa to w czasie pseudo-quasi-liniowym * i wykorzystuje stwierdzenie OEIS, że

Transformacja Moebiusa jest sekwencją okresu 4 [4, 0, -4, 0, ...]. - Michael Somos, 17 września 2007 r

Wkład 0jest oczywiście szczególnym przypadkiem (transformacje Möbiusa i anihilatory nie idą w parze), ale ostatecznie kosztuje tylko jeden znak.

* Pseudo - ponieważ jest quasilinearny w wartości wejściowej, a nie w wielkości wejściowej; quasi, ponieważ wykonuje Theta(n)operacje na liczbach całkowitych wielkości w kolejności n; boperacja -bitowa mod powinien wziąć b lg bczas, więc ogólnie rzecz biorąc to bierze Theta(n lg n lg lg n)czas.

Peter Taylor
źródło
6

Japt , 42 37 33 bajtów

Japt to skrócona wersja Ja vaScri pt . Interpretator

V=Un oU+1;Vr@X+(Vf_p2 +Y*Y¥U)l ,0

Jak to działa

           // Implicit: U = input number
V=Un oU+1  // Set variable V to range(-U, U+1). Ends up like [-U,-U+1,...,U-1,U]
Vr@    ,0  // Reduce each item Y in V with this function, starting at 0:
X+(     l  //  Return the previous value X + the length of:
Vf_p2      //   V filtered by items Z where Z*Z
+Y*Y==U)   //    + Y*Y equals U.
           // This ends up as the combined length of all fitting pairs of squares.
           // Implicit: return last expression

Być może istnieje lepsza technika; sugestie są mile widziane.

ETHprodukcje
źródło
6

Python 3, 68 61 60 bajtów

lambda n:0**n+4*sum(i**.5%1+(n-i)**.5%1==0for i in range(n))

Korzystanie z dwóch zestawień zagnieżdżonych list jest zbyt drogie. Zamiast tego sprawdza, czy obie współrzędne na okręgu o promieniu sqrt (n) są liczbami całkowitymi.

Peter Taylor pokonał to dzięki podejściu opartemu na inwersji Moebiusa .

lirtosiast
źródło
Dobra robota. Majstrowałem przy funkcji rekurencyjnej, ale nie mogłem n=0elegancko rozwiązać .
xsot
5

Oktawa, 28 bajtów

@(n)nnz((a=(-n:n).^2)'+a==n)
alephalpha
źródło
5

Haskell, 42 bajty

f n|q<-[-n..n]=sum[1|a<-q,b<-q,a*a+b*b==n]

Przykład użycia:

*Main> map f [0..25]
[1,4,4,0,4,8,0,0,4,4,8,0,0,8,0,0,4,8,4,0,8,0,0,0,0,12]
*Main> 
nimi
źródło
3
Wiązanie qw straży jest sprytne, zapamiętam tę sztuczkę.
xnor
5

Julia, 89 79 63 bajtów

g(x)=cos(π*x^.5)^2÷1
a(n)=(n==0)+4sum([g(i)g(n-i)for i=1:n])

Jest to nazwana funkcja, aktóra przyjmuje liczbę całkowitą i zwraca liczbę zmiennoprzecinkową. Wywołuje funkcję pomocnika g.

Nie golfowany:

function g(x::Integer)
    floor(cos(π*sqrt(x))^2)
end

function a(n::Integer)
    (n == 0) + 4*sum([g(i)*g(n-i) for i=1:n])
end

Podejście to wykorzystuje uproszczenie wzoru Wesleya Ivana Hurta wymienionego w OEIS. Uproszczenie zostało znalezione przez Glen O, tę samą osobę, która straciła 26 bajtów tej odpowiedzi!

Alex A.
źródło
Użyj x^.5zamiast, sqrt(x)aby zapisać 3 bajty. I (n==0)oszczędza 2 bajty 1÷(n+1). I możesz zapisać 4 dodatkowe znaki, używając cos(π*sqrt(x))^2÷1zamiast floor(cos(π*sqrt(x))^2). Używaj 1:n/2raczej niż 1:n÷2, ponieważ nie ma żadnej szkody przy użyciu pływaka w g(x)i tak czy inaczej zostanie on zablokowany na liczbach całkowitych i. I sum(i->g(i)g(n-i),1:n/2)ogolą jeszcze kilka postaci.
Glen O
@GlenO Świetne sugestie, dzięki. sumSztuczka nie powiedzie się n=0jednak, więc trzymałem tablicę ze zrozumieniem.
Alex A.,
1
Tak więc można go odzyskać - jeśli pozwolisz, aby i=0sprawa zdarzyła się łącznie, możesz włączyć znak 4g(n). Tak więc (n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2), który nie popełni błędu. Ale możesz zrobić jeszcze lepiej, odnotowując symetrie -(n==0)+4sum([g(i)g(n-i)for i=1:n])
Glen O
@GlenO To uproszczenie jest poważnie geniuszem. Polecam przesłać to jako alternatywną formułę sekwencji w OEIS!
Alex A.,
4

Pyth, 16 15 bajtów

lfqQs^R2T^}_QQ2

Wypróbuj online w kompilatorze Pyth .

Jak to działa

lfqQs^R2T^}_QQ2

          }_QQ   Compute the inclusive range from -Q to Q (input).
         ^    2  Take the second Cartesian power, i.e., compute all pairs.
 f               Filter; for each T in the list of pairs:
     ^R2T          Compute the squares of T's elements.
    s              Add the squares.
  qQ               Compare the sum with Q.
                 If q returned True, keep T.
l                Count the kept pairs.
Dennis
źródło
4

TI-BASIC, 23 bajty

sum(seq(Σ(X²+Y²=Ans,X,-Ans,Ans),Y,-Ans,Ans

Całkiem proste. Σ(to sumowanie.

O dziwo sum(seq(sum(seq(rzuca ERR:ILLEGAL NESTi tak samo Σ(Σ(, ale sum(seq(Σ(jest w porządku. Zdecydowałem się umieścić Σ(wnętrze, aby uratować bliskie miąższ.

lirtosiast
źródło
Jaka jest różnica między sumi Σ?
alephalpha
1
@alephalpha Σ (pobiera sumę, sumując wszystkie X²+Y²=Answartości X między -Ansi Ans. suma (jest sumą listy , więc musimy najpierw utworzyć listę za pomocą seq (..., Y, -Ans, Ans
lirtosiast
4

JavaScript (ES6), 66 60 bajtów

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

6 bajtów zapisanych dzięki @ edc65 !

Wyjaśnienie

n=>eval(`              // use eval to allow for loops in an unparenthesised arrow function
  for(r=0,             // r = number of pairs
    a=~n;a++<n;        // a = first number to square
  )
      for(b=~n;b++<n;) // b = second number to square
        r+=a*a+b*b==n  // add one to the result if a^2 + b^2 == n
                       // implicit: return r
`)

Test

n = <input type="number" oninput='result.innerHTML=(

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

)(+this.value)' /><pre id="result"></pre>

użytkownik 81655
źródło
1
60:n=>eval('for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n')
edc65
@ edc65 Fajnie! I nie myśleć o użyciu evalumieścić forpętle do funkcji strzałki bez nawiasów. Zapomniałem również o ~haha operatora.
user81655,
4

Python 3, 93 62 69 bajtów

Itertools nie działały, więc ponownie użyłem dwóch zakresów, ale przesunąłem zakres, aby zapisać bajty.

Edycja: Poprzedni kod tak naprawdę nie działał, ponieważ zdefiniowałem zakres powyżej n, zanim zdefiniowałem n.

lambda n:sum(i*i+j*j==n for i in range(-n,n+1)for j in range(-n,n+1))
Sherlock9
źródło
2

APL, 23 20 19 bajtów

{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}

Wyjaśnienie:

{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}        Monadic function:
                 ⍳⍵          1 2 3 ... ⍵
               ,⍨            Duplicate
             0,              Concatenate to 0
          ×⍨                 Square everything
      ∘.+⍨                   Make an addition table
     ∊                       Flatten
   ⍵=                        1s where equal to the input
 +/                          Sum up the 1s

Poza tym, że APL nie ma funkcji J i:(liczby od -n do n), działa to prawie tak samo jak odpowiedź J.

Nie możemy korzystać z pociągu, ponieważ wykonanie -\⍳2×⍵polecenia „nie parsuj” (-\) ⍳ (2×⍵)kosztuje trzy bajty; podobnie z inną parą atops. Wszystkie te nawiasy skracają normalną funkcję.

Wypróbuj tutaj . Dane wyjściowe 1oznaczają, że wszystkie wartości są zgodne.

lirtosiast
źródło
2

Matlab 41 bajtów

Jeszcze mniejszy niż poprzednie odpowiedzi

@(n)nnz(~mod(sqrt(n-(1:n^.5).^2),1))*4+~n

Zasadniczo odpowiedź Agawa001 z zastąpieniem power i sqrt

Jonas
źródło
2

Candy , 17 14 bajtów

Dane wejściowe wypychane początkowo na stos

~TbAT1C(sWs+Aeh)Z

~T0C(sWs+Aeh)Z

peekA    # copy arg from stack to register A
range2   # create double sided range on stack, -A, 1-A, ... A-1, A
digit0   # prefix argument to 'cart', 
cart     # cartesian product of current stack(0), and other stack(0)
while    # while stack not empty
  sqr    # pop and square and push
  swap   # swap two stack elements
  sqr    # pop and square and push
  add    # pop and pop and add and push
  pushA  # push original argument
  equal  # equality test 0/1
  popAddZ  # Z := Z + pop
endwhile
pushZ    # push Z onto stack, will be output to stdout on termination
Dale Johnson
źródło
2

CJam, 28

qi_mF{3a>},{~)\4%2-&}%4+:*1?

Niezbyt krótki, ale wydajny. Np. Wynik dla 15625 wynosi natychmiast 28. Wykorzystuje wzór oparty na faktoryzacji z OEIS.
Wypróbuj online

Wyjaśnienie:

qi       read input and convert to integer
_        make a copy (will be used to handle the 0 case at the end)
mF       factorize into [prime exponent] pairs
{…},     filter the array of pairs
  3a>    with the condition that the pair is greater than [3]
          which means the prime factor must be ⩾3
{…}%     transform each pair as follows:
  ~      dump the prime factor and exponent onto the stack
  )      increment the exponent
  \      swap with the prime
  4%     get the remainder mod 4 (it will be 1 or 3)
  2-     subtract 2 (resulting in -1 or 1)
  &      bitwise AND with the incremented exponent (see below)
4+       append a 4 to the array
:*       multiply all
1?       if the input was 0, use 1, else use the above result

Niektóre szczegóły dotyczące obliczeń:

  • jeśli liczbą pierwszą jest 1 mod 4, kod oblicza (exponent + 1) & -1, co jestexponent + 1
  • jeśli liczbą pierwszą jest 3 mod 4, kod oblicza (exponent + 1) & 1, która wynosi 0, jeśli wykładnik jest nieparzysty, a 1, jeśli parzysty

Wszystkie te wartości pomnożone razem i pomnożone przez 4 są dokładnie formułą OEIS.

aditsu
źródło
2

Python 2, 68 bajtów

def x(n):r=range(-n,n+1);print sum(a*a+b*b==n for a in r for b in r)

Definiuje wywoływaną funkcję, x()która przyjmuje liczbę n.

Wypróbuj online. http://ideone.com/aRoxGF

Rɪᴋᴇʀ
źródło
Brakuje instrukcji printlub return.
Zgarb
Dzięki, zupełnie zapomniałem. Link ma jednak instrukcję print. Edytowałem kod podczas jego tworzenia.
Rɪᴋᴇʀ
Ok nie martw się. Ale wydaje się to również dawać niepoprawne wyniki dla n=0i n=1(0 i 2 zamiast 1 i 4). Może limity zasięgu wymagają dostosowania?
Zgarb
@Zgarb Tak, powinny kończyć się na n+1.
lirtosiast
1
Poszukam tego.
Rɪᴋᴇʀ
2

Pyth, 41 35 33 30 27 bajtów

Wypróbuj online.

Edycja: Dzięki isaacg mam mi *Fdo pracy! TAK!

?Q*F+4m.&tt%ed4hhdr-PQ2 8 1
                                (implicit) Q = input()
?Q                              If Q != 0
      m                           Map to d (exponent, prime) from ...
                  r-PQ2 8         run-length-encoded(PQ with 2's removed)
       .&                           Bitwise and
           %ed4                       d[-1] % 4
         tt                           -2
                hd                  with d[0]
               h                      +1
    +4                            Append 4 to the resulting array
  *F                              Then multiply it all together
                          1     Else 1

Edycja: włóż bit bit i wróć, aby uzyskać więcej oszczędności bajtów! Usunąłem też wszystkie „dawniej” rzeczy. Zaczynało się zagracać.

Dzięki aditsu i jego rozwiązaniu CJam oraz maltysen i jego wskazówkom (Pewnego dnia zabiorę się m*Fddo pracy. Pewnego dnia ...)

J4Vr-PQ2 8=J*J.&tt%eN4hhN;?QJ1
                                (implicit) Q=input()
J4                              J=4
    -PQ2                        Remove all 2's from the prime factorization of Q
   r     8                      run-length encode (exponent, prime factor)
  V                      ;      For N in range( the above ):
          =J*J                      J = J * ...
                tt%eN4                N[-1] mod 4 -2 
                      hhN             (exponent + 1)
              .&                    bitwise and
                          ?QJ1  if Q != 0 print(J) else print(1)

Zauważ, że

  • jeśli liczbą pierwszą jest 1 mod 4, otrzymujemy -1 & (exponent + 1), co jestexponent + 1

  • ale jeśli liczbą pierwszą jest 3 mod 4, otrzymujemy 1 & (exponent + 1), to znaczy, 0jeśli wykładnik jest nieparzysty, a 1nawet parzysty

Pomnóż to wszystko razem (razy 4 na początku), a otrzymamy sumę dwóch kwadratów, które składają się na nasz wkład.

Sherlock9
źródło
2

Python, 57 bajtów

Niezłe wyzwanie. Niestety w tej chwili nie jestem krótszy.

lambda n:0**n+sum(2-d%4for d in range(1,n+1)if d%2>n%d)*4
Willem
źródło
2

PARI / GP, 34 28 bajtów

Korzystanie z funkcji generowania:

Zaoszczędź 6 bajtów dzięki Mitchowi Schwartzowi .

n->sum(i=-n,n,x^i^2)^2\x^n%x

Przy użyciu wbudowanych 33 bajtów (zapisano 1 bajt dzięki Mitchowi Schwartzowi ):

n->if(n,2*qfrep(matid(2),n)[n],1)

qfrep (q, B, {flag = 0}): wektor (połowy) liczby wektorów norm od 1 do B dla integralnej i określonej postaci kwadratowej q. Jeśli flaga ma wartość 1, policz wektory parzystej normy od 1 do 2B.


alephalpha
źródło
matid(2)zapisuje bajt.
Mitch Schwartz,
1
I do 28 dla podejścia do funkcji generowania:n->sum(i=-n,n,x^i^2)^2\x^n%x
Mitch Schwartz,
1

Matlab, 72 bajty

n=input('');m=fix(sqrt(n));m=(-m:m).^2;disp(nnz(bsxfun(@plus,m,m')==n))
Luis Mendo
źródło
W tym wyzwaniu nie potrzebujeszdisp Luis! =)
Stewie Griffin
@StewieGriffin Thanks! Ale w tym przypadku jest to program, a nie funkcja. Więc zgodnie z zaakceptowaną odpowiedzią w twoim linku jest to potrzebne, prawda?
Luis Mendo,
1

Matlab, 63 50 bajtów

@(y)nnz(~mod(sqrt(y-power((1:sqrt(y)),2)),1))*4+~y

  • To pobija drugi kod o tym samym tytule, dlatego go umieszczam: D.

  • Program znajduje pozytywne rozwiązania liczb całkowitych, a następnie pomnoży je przez 4, aby objąć rozwiązania negatywne.

  • Może wykonać wszystkie 25 pierwszych przypadków testowych

    for i=1:25 ans(i)
    end
    
       1
    
       4
    
       4
    
       0
    
       4
    
       8
    
       0
    
       0
    
       4
    
       4
    
       8
    
       0
    
       0
    
       8
    
       0
    
       0
    
       4
    
       8
    
       4
    
       0
    
       8
    
       0
    
       0
    
       0
    
       0
    
       12
    
Abr001am
źródło
W tym wyzwaniu nie potrzebujeszdisp ! =)
Stewie Griffin
dzięki @StewieGriffin załączyłem to jako uczciwą grę związaną z
Luisem
Wskazówki: Kiedy planujesz opublikować wyniki z MATLAB, użyj format compact=)
Stewie Griffin
1

JavaScript, 89 bajtów

n=prompt()
p=Math.pow
for (x=c=(+n?0:1);x<=n;x++)if(x&&p(n-p(x,2),.5)%1===0)c+=4
alert(c)

Wiem, że nie jest to najkrótsza odpowiedź JavaScript, nawet gdybym usunęła linie we / wy, ale myślę, że jest to najlepiej działająca odpowiedź JS, dająca mi wynik za milion w ciągu kilku sekund (dziesięć milionów zajęło około minuta).

Adam Dally
źródło
Czy możesz użyć == zamiast ===?
lirtosiast
Mógłbym, stosując najlepsze praktyki, ha ha.
Adam Dally,
1

PHP, 70 bajtów, nie konkuruje

for($x=-1;$x++<=$n=$argv[1];)$s+=(-($n%($x-~$x)<1))**$x*4;echo$n?$s:1;

algorytm skradziony jednej z odpowiedzi w języku Python ... Zapomniałem, która z nich; chciałem przynajmniej częściowo zrozumieć, co się dzieje, zanim opublikowałem.

Tytus
źródło
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;zapisuje 5 bajtów. $x-~$xjest równa 2*$x+1i możesz teraz rozpocząć bez przypisywania zmiennej.
Jörg Hülsermann