Zähle die Summe zweier Quadrate

45

Bei einer nicht negativen Zahl ngeben Sie die Anzahl der Ausdrücke nals Summe von zwei Quadraten mit ganzen Zahlen aus n == a^2 + b^2( OEIS A004018 ). Beachten Sie, dass aund bpositiv, negativ oder null sein kann und deren Reihenfolge von Bedeutung ist. Wenigste Bytes gewinnt.

Zum Beispiel n=25gibt, 12weil 25ausgedrückt werden kann als

(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

Hier sind die Werte bis zu n=25. Achten Sie darauf, dass Ihr Code funktioniert 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

Hier sind die Werte bis n=100als Liste aufgeführt.

[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]

Wissenswertes: Die Sequenz enthält Begriffe, die willkürlich hoch sind, und die Grenze ihres laufenden Durchschnitts ist π.

Bestenliste:

Code-Snippet anzeigen

code-golf math combinatorics number-theory xnor
quelle
4
Warte was?? "Die Sequenz enthält Begriffe, die willkürlich hoch sind, und die Grenze ihres laufenden Durchschnitts ist π."
Stewie Griffin
@StewieGriffin Die beiden Aussagen stimmen überein. Betrachten Sie die Reihenfolge 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Wenn die Sequenz nach einer Zahl ungleich Null abgeschnitten wird, ist der bisherige Durchschnitt 1. Und die Läufe von Nullen haben später in der Sequenz immer weniger Einfluss.
26.
5
Ich weiß, dass es konsistent ist. =) Ich hatte die 10.000 ersten Zahlen überprüft, als ich den Kommentar gepostet habe. Was ich nicht verstehe ist: Warum um alles in der Welt ist es gleich Pi?
Stewie Griffin
29
@StewieGriffin Die Summe der Terme bis N entspricht den Punkten (a, b) mit a ^ 2 + b ^ 2 <= N. Dies sind die Gitterpunkte im Kreis mit dem Radius sqrt (N), dessen Fläche πN ist.
26.
2
@ Xnor und es geht die Magie :(
Andras Deak

Antworten:

19

Python ( 59 57 56 Bytes)

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

Online-Demo

Wie bei meiner CJam-Antwort wird die Möbius-Inversion verwendet und in pseudoquasilinearer Zeit ausgeführt.

Dank Sp3000 für die Einsparungen von 2 Byte und feersum für 1 Byte .

Peter Taylor
quelle
1
Diese Klammern nerven.
Lirtosiast
@ ThomasKwa, erzähl mir davon. Was mich wirklich überrascht hat, war, dass es in einer der Versionen, die ich auf dem Weg zu der ersten Version, die ich gepostet habe, durchlaufen habe, -1**ximmer so war -1. Ich habe erwartet -1, dass es sich bei dem Zeichen um ein einzelnes Ganzzahl-Literal handelt und nicht um ein unäres Minus mit niedriger Priorität, gefolgt von einer Eins.
Peter Taylor
2
Herzlichen Glückwunsch zu der Prämie! Ihr Code ist kürzer als alles, was ich mir ausgedacht habe. Ihre Lösung basiert auf einer völlig neuen und unerwarteten mathematischen Idee, und ich freue mich, dass dies auch bei einer so geradlinigen Herausforderung möglich ist. Das Mobius-inverse Ergebnis ist ziemlich hübsch, und ich habe mir die Freude genommen, einen Beweis dafür abzuleiten mich selber.
5.
1 Byte kann durch Verschieben der Multiplikation mit 4 nach nach gespeichert werden **x.
Feersum
@PeterTaylor Können Sie erläutern, wie Ihr Algorithmus funktioniert, / können Sie mich auf eine Ressource verweisen? Ich kann nicht genau sagen, wie Sie die Möbius-Umkehrung auf die Anzahl der Summen von suqares Problem anwenden können.
Fehler
15

Mathematica, 13 Bytes

Wenn eingebaute Funktionen zulässig sind, geschieht dies in Mathematica.

2~SquaresR~#&

Für 0 <= n <= 100

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

{1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 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, 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
quelle
1
Da hat Mathematica natürlich eine eingebaute.
HyperNeutrino
14

Python 2, 44 Bytes

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

Dies ist fast dasselbe wie die Lösung von xsot (die auf der Lösung von Peter Taylor basiert ), spart jedoch 8 Byte, indem die Art und Weise vereinfacht wird, wie Zeichen behandelt werden.

Beachten Sie, dass wir für ein vollständiges Programm 2 Bytes in der Funktion einsparen können, ohne dass Kosten außerhalb der Funktion anfallen:

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

Zwei zusätzliche Bytes für ein volles Programm auf diese Weise:

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

Denn n > 0es gibt eine gut lesbare 40-Byte-Lösung:

f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)
Mitch Schwartz
quelle
1
Herzlichen Glückwunsch zum Gewinn der Prämie! Die rekursive Subtraktion ist eine saubere und kurze Methode, um die alternierende Summe für ungerade Teiler auszudrücken, ohne ein Vorzeichen aus dem Teiler selbst extrahieren zu müssen. Wir danken auch xsot für die Rationalisierung von Peter Taylors Lösung auf eine rekursive Lösung mit einer geschickten Behandlung von n = 0.
xnor
12

Pyth, 13 Bytes

/sM^^R2}_QQ2Q

Testsuite

/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
quelle
Spät, aber ich glaube nicht, dass Sie das Letzte brauchen Q.
Erik der Outgolfer
12

J, 16 Bytes

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

Dies ist ein monadisches Verb (mit anderen Worten eine unäre Funktion). Probieren Sie es online aus oder sehen Sie, ob alle Testfälle bestanden wurden .

Erläuterung

+/@,@:=+&*:/~@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
quelle
11

Python 2, 69 55 53 52 Bytes

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

Dies ist eine rekursive Funktion, die auf der exzellenten Lösung von Peter Taylor basiert .

xsot
quelle
1
Dies ist eine große Verbesserung. Aber es gibt immer noch eine Möglichkeit, es zu verkürzen, und ich ermutige Sie, danach zu suchen.
xnor
1
@xnor Ein weiteres Byte nach unten. Ich hoffe du hast keine Tricks mehr im Ärmel.
Xsot
2
Ich weiß nicht , ob ich eine Antwort daraus machen, es ist nur Ihre Lösung plus ein Trick: f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2. Außerdem ist es uns wohl egal, ob die standardmäßige maximale Rekursionstiefe überschritten wird.
Mitch Schwartz
1
@MitchSchwartz Ich denke, das ist eine unglaubliche Verbesserung, die es wert ist, belohnt zu werden und wahrscheinlich die endgültige Optimierung, die xnor im Sinn hatte.
Xsot
1
@MitchSchwartz Ja, das ist die Optimierung, an die ich gedacht habe! Und xsots /4<<2Trick macht es kürzer als das, was ich hatte.
9.
8

Julia, 40 Bytes

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

Ungolfed:

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

Beachten Sie, dass die Schleife nicht enthält i==0 , da, wenn nes sich um ein Quadrat handelt, dieses bereits von eingeschlossen i=sqrt(n)ist und es für dieses Formular nur vier und keine acht gibt ( 0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2).

Glen O
quelle
7

CJam, 25 23 Bytes

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

Dies ist eine theoretische Lösung, die O (9 n benötigt ) Zeit und Speicher für die Eingabe von n benötigt .

Auf Kosten eines zusätzlichen Bytes - für insgesamt 24 Bytes - können wir die Komplexität auf O (n 2 reduzieren ) :

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

Probieren Sie es online!

Wie es funktioniert

Entweder

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

oder

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

Dann

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
quelle
Und bei einer Einsparung von einem Byte ist es möglich, die Komplexität auf Õ (n) zu reduzieren
Peter Taylor
Ja, ich habe gesehen. Das ist erstaunlich.
Dennis
7

CJam ( 25 24 22 21 Bytes)

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

Online-Demo

Dieser läuft in pseudoquasilinearer Zeit * und verwendet die Anweisung des OEIS that

Die Moebius-Transformation ist eine Sequenz der Periode 4 [4, 0, -4, 0, ...]. - Michael Somos, 17. September 2007

Die Eingabe 0 ist offensichtlich ein Sonderfall (Möbius-Transformationen und -Vernichter passen nicht gut zusammen), hat jedoch nur ein Zeichen gekostet.

* Pseudo- weil es im Wert der Eingabe quasilinear ist, nicht in der Größe der Eingabe; quasi, weil es Theta(n)Operationen mit ganzen Zahlen in der Größenordnung von ausführt n; Eine b-bit-Mod-Operation sollte einige Zeit in Anspruch nehmen b lg b, daher dauert dies insgesamt einige Theta(n lg n lg lg n)Zeit.

Peter Taylor
quelle
6

Japt , 42 37 33 Bytes

Japt ist eine verkürzte Version von Ja vaScri pt . Dolmetscher

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

Wie es funktioniert

           // 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

Vielleicht gibt es eine bessere Technik; Vorschläge sind willkommen.

ETHproductions
quelle
6

Python 3, 68 61 60 Bytes

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

Die Verwendung von zwei verschachtelten Listenverständnissen ist zu teuer. Stattdessen wird geprüft, ob beide Koordinaten auf dem Kreis mit dem Radius sqrt (n) Ganzzahlen sind.

Peter Taylor hat dies mit einem Moebius-Inversion-basierten Ansatz geschlagen .

Lirtosiast
quelle
Gut gemacht. Ich bastelte an einer rekursiven Funktion, konnte sie aber nicht n=0elegant auflösen .
xsot
5

Oktave, 28 Bytes

@(n)nnz((a=(-n:n).^2)'+a==n)
Alephalpha
quelle
5

Haskell, 42 Bytes

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

Anwendungsbeispiel:

*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
quelle
3
Es qist klug, eine Wache einzubinden, ich werde mich an diesen Trick erinnern.
26.
5

Julia, 89 79 63 Bytes

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

Dies ist eine benannte Funktion, adie eine Ganzzahl akzeptiert und einen Gleitkommawert zurückgibt. Es ruft eine Hilfsfunktion auf g.

Ungolfed:

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

Bei diesem Ansatz wird eine Vereinfachung der in OEIS aufgeführten Formel von Wesley Ivan Hurt verwendet. Die Vereinfachung wurde von Glen O, der gleichen Person, die 26 Bytes dieser Antwort rasiert hat, gefunden!

Alex A.
quelle
Verwenden Sie x^.5statt sqrt(x)3 Bytes zu speichern. Und (n==0)spart 2 Bytes mehr 1÷(n+1). Und Sie können 4 weitere Zeichen speichern, indem Sie cos(π*sqrt(x))^2÷1anstatt verwenden floor(cos(π*sqrt(x))^2). Verwenden Sie auch 1:n/2lieber als 1:n÷2, da die Verwendung eines Float-Ins keinen Schaden anrichtet g(x)und es iohnehin für die ganzen Zahlen gesperrt wird. Und sum(i->g(i)g(n-i),1:n/2)wird auch noch ein paar Charaktere rasieren.
Glen O
@ GlenO Tolle Vorschläge, danke. Der sumTrick schlägt jedoch fehl n=0, sodass ich das Array-Verständnis beibehalten habe.
Alex A.
1
So kann es wiederhergestellt werden - wenn Sie den i=0Fall in der Summe passieren lassen , können Sie das Zeichen einschalten 4g(n). Also (n==0)-4g(n)-4g(n/2)+8sum(i->g(i)g(n-i),0:n/2), was wird nicht in den Fehler laufen. Aber Sie können es noch besser machen, indem Sie die Symmetrien notieren -(n==0)+4sum([g(i)g(n-i)for i=1:n])
Glen O
@ GlenO Diese Vereinfachung ist ernsthaft genial. Ich empfehle Ihnen, das als alternative Formel für die Sequenz auf OEIS einzureichen!
Alex A.
4

Pyth, 16 15 Bytes

lfqQs^R2T^}_QQ2

Versuchen Sie es online im Pyth-Compiler .

Wie es funktioniert

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
quelle
4

TI-BASIC, 23 Bytes

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

Ziemlich einfach. Σ(ist Summation.

Seltsamerweise sum(seq(sum(seq(wirft ein ERR:ILLEGAL NEST, und tut es auch Σ(Σ(, ist aber sum(seq(Σ(in Ordnung. Ich entschied mich für Σ(die Innenseite, um ein enges Verhältnis zu wahren.

Lirtosiast
quelle
Was ist der Unterschied zwischen sumund Σ?
alephalpha
1
@alephalpha Σ (Summiert alle X²+Y²=AnsWerte von X zwischen -Ansund Ans. sum (ist die Summe einer Liste. Daher müssen wir die Liste zuerst mit seq (..., Y, -Ans, Ans
Lirtosiast
4

JavaScript (ES6), 66 60 Bytes

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

6 Bytes gespart dank @ edc65 !

Erläuterung

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
`)

Prüfung

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>
Erweitern Sie das Snippet

user81655
quelle
1
60:n=>eval('for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n')
edc65
@ edc65 Schön! Ich habe nicht daran gedachteval , die forSchleifen in eine Pfeilfunktion ohne Klammern zu setzen. Ich habe auch den ~Operator vergessen haha.
User81655
4

Python 3, 93 62 69 Bytes

Itertools funktionierte nicht, also habe ich wieder zwei Bereiche verwendet, aber den Bereich herausgezogen, um Bytes zu sparen.

Bearbeiten: Vorheriger Code hat nicht wirklich funktioniert, da ich einen Bereich über n definiert habe, bevor ich n definiert habe.

lambda n:sum(i*i+j*j==n for i in range(-n,n+1)for j in range(-n,n+1))
Sherlock9
quelle
2

APL, 23 20 19 Bytes

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

Erläuterung:

{+/⍵=∊∘.+⍨×⍨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

Abgesehen von der Tatsache, dass APL keine J's hat i: (Zahlen von -n bis n) hat, funktioniert dies ziemlich ähnlich wie die J-Antwort.

Wir können keinen Zug benutzen, weil wir das -\⍳2×⍵nicht analysieren wollen(-\) ⍳ (2×⍵) drei Bytes kosten würde; Ähnliches gilt für andere Atops. Alle diese Klammern verkürzen die reguläre Funktion.

Probieren Sie es hier aus . Die Ausgabe von 1bedeutet, dass alle Werte übereinstimmen.

Lirtosiast
quelle
2

Matlab 41 Bytes

Noch kleiner als die vorherigen Antworten

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

Grundsätzlich wurde die Antwort von Agawa001 durch power und sqrt ersetzt

Jonas
quelle
2

Süßigkeiten , 17 14 Bytes

Die Eingabe wurde zunächst auf den Stapel geschoben

~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
quelle
2

CJam, 28

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

Nicht wirklich kurz, aber effizient. ZB ist das Ergebnis für 15625 sofort 28. Verwendet die auf Faktorisierung basierende Formel von OEIS.
Probieren Sie es online aus

Erläuterung:

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

Einige Details zur Berechnung:

  • Wenn die Primzahl 1 mod 4 ist, berechnet der Code (exponent + 1) & -1 , was istexponent + 1
  • Wenn die Primzahl 3 mod 4 ist, berechnet der Code (exponent + 1) & 1 0, wenn der Exponent ungerade ist, und 1, wenn gerade

Alle diese Werte multipliziert und multipliziert mit 4 sind genau die OEIS-Formel.

aditsu
quelle
2

Python 2, 68 Bytes

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

Definiert eine aufgerufene Funktion x() , die eine Nummer n annimmt.

Probieren Sie es online aus. http://ideone.com/aRoxGF

Rɪᴋᴇʀ
quelle
Sie vermissen eine printoder returnAussage.
Zgarb
Danke, ich habe es komplett vergessen. Der Link hat jedoch die print-Anweisung. Ich habe meinen Code bearbeitet, während ich den Code erstellt habe.
28.
Ok, keine Sorge. Dies scheint aber auch falsche Ergebnisse für n=0und zu liefern n=1(0 und 2 statt 1 und 4). Möglicherweise müssen die Bereichsgrenzen angepasst werden?
Zgarb
@ Zgarb Ja, sie sollten um enden n+1.
Lirtosiast
1
Ich werde danach suchen.
29.
2

Pyth, 41 35 33 30 27 Bytes

Probieren Sie es online aus.

Edit: Dank isaacg habe ich bekommen mund *Fzu arbeiten! JA!

?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

Bearbeiten: Setzen Sie die bitweise und wieder für mehr Byte-Einsparungen! Außerdem habe ich alles "Früher" entfernt. Es wurde langsam unübersichtlich.

Dank an Aditsu und seine CJam-Lösung und an Malzsen und seine Tipps (Eines Tages werde ich m*Fdzur Arbeit gehen. Eines Tages ...)

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)

Beachten Sie, dass,

  • Wenn die Primzahl 1 mod 4 ist, bekommen wir -1 & (exponent + 1), was istexponent + 1

  • aber wenn die Primzahl 3 mod 4 ist, erhalten wir 1 & (exponent + 1), 0wenn der Exponent ungerade und 1wenn gerade ist

Multiplizieren Sie alles (zu Beginn mit 4), und Sie erhalten die Summe von zwei Quadraten, die sich zu unserer Eingabe addieren.

Sherlock9
quelle
2

Python, 57 Bytes

Schöne Herausforderung. Leider werde ich es im Moment nicht kürzer.

lambda n:0**n+sum(2-d%4for d in range(1,n+1)if d%2>n%d)*4
Willem
quelle
2

PARI / GP, 34 28 Bytes

Generierungsfunktionen verwenden:

6 Bytes gespart dank Mitch Schwartz .

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

Mit eingebauten 33 Bytes (dank Mitch Schwartz 1 Byte gespart ):

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

qfrep (q, B, {flag = 0}): Vektor der (halben) Anzahl von Vektoren der Normen von 1 bis B für die ganzzahlige und bestimmte quadratische Form q. Wenn flag 1 ist, werden Vektoren mit gerader Norm von 1 bis 2B gezählt.

Alephalpha
quelle
matid(2)Speichert ein Byte.
Mitch Schwartz
1
Und bis auf 28 für den Ansatz der generierenden Funktion:n->sum(i=-n,n,x^i^2)^2\x^n%x
Mitch Schwartz
1

Matlab, 72 Bytes

n=input('');m=fix(sqrt(n));m=(-m:m).^2;disp(nnz(bsxfun(@plus,m,m')==n))
Luis Mendo
quelle
Du brauchst dispin dieser Herausforderung nicht Luis! =)
Stewie Griffin
@StewieGriffin Danke! In diesem Fall handelt es sich jedoch um ein Programm und nicht um eine Funktion. Entsprechend der akzeptierten Antwort in Ihrem Link wird es also benötigt, nicht wahr?
Luis Mendo
1

Matlab, 63 50 Bytes

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

  • Dies schlägt den anderen gleichberechtigten Code, also sage ich es: D.

  • Das Programm ermittelt die positiven ganzzahligen Lösungen und multipliziert sie mit 4, um negative Lösungen einzuschließen.

  • Es können alle 25 ersten Testfälle durchgeführt werden

    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
quelle
Das brauchstdisp du bei dieser Herausforderung nicht ! =)
Stewie Griffin
danke @StewieGriffin Ich habe es nur als ein faires Spiel in Bezug auf Luis 'One aufgenommen
Abr001am
Tipps: Wenn Sie die Ergebnisse von MATLAB veröffentlichen möchten, verwenden Sie format compact=)
Stewie Griffin,
1

JavaScript, 89 Bytes

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)

Ich weiß, dass dies nicht die kürzeste JavaScript-Antwort ist, selbst wenn ich die E / A-Zeilen entfernen würde, aber ich denke, es ist die am besten funktionierende JS-Antwort, die mir das Ergebnis für eine Million innerhalb weniger Sekunden liefert (zehn Millionen haben ungefähr eine Sekunde gedauert) Minute).

Adam Dally
quelle
Können Sie == anstelle von === verwenden?
Lirtosiast
Ich könnte, nur mit Best Practices, ha ha.
Adam Dally
1

PHP, 70 Bytes, nicht konkurrierend

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

Algorithmus aus einer der Python-Antworten gestohlen ... Ich habe vergessen, welche; wollte zumindest teilweise verstehen was passiert bevor ich gepostet habe.

Titus
quelle
for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1;spart 5 Bytes. $x-~$xist gleich 2*$x+1und Sie können jetzt beginnen, ohne die Variable zuzuweisen.
Jörg Hülsermann