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.

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:

Pokaż fragment kodu

    var QUESTION_ID=64812,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/64812/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

    body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

Rozwiń fragment kodu

— 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

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 ⁿ ) 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 ² ) :

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>

Rozwiń fragment kodu

— 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

Policz sumy dwóch kwadratów

Python ( 59 57 56 bajtów)

Mathematica, 13 bajtów

Python 2, 44 bajty

Pyth, 13 bajtów

J, 16 bajtów

Wyjaśnienie

Python 2, 69 55 53 52 bajty

Julia, 40 bajtów

CJam, 25 23 bajtów

Jak to działa

CJam ( 25 24 22 21 bajtów)

Japt , 42 37 33 bajtów

Jak to działa

Python 3, 68 61 60 bajtów

Oktawa, 28 bajtów

Haskell, 42 bajty

Julia, 89 79 63 bajtów

Pyth, 16 15 bajtów

Jak to działa

TI-BASIC, 23 bajty

JavaScript (ES6), 66 60 bajtów

Wyjaśnienie

Test

Python 3, 93 62 69 bajtów

APL, 23 20 19 bajtów

Matlab 41 bajtów

Candy , 17 14 bajtów

CJam, 28

Python 2, 68 bajtów

Pyth, 41 35 33 30 27 bajtów

Python, 57 bajtów

PARI / GP, 34 28 bajtów

Matlab, 72 bajty

Matlab, 63 50 bajtów

JavaScript, 89 bajtów

PHP, 70 bajtów, nie konkuruje