Es ist altbekannt, dass jede nicht negative ganze Zahl als die Summe von vier quadratischen ganzen Zahlen umgeschrieben werden kann. Beispielsweise kann die Zahl 1 als $0^2+0^2+0^2+1^2$ ausgedrückt werden . Oder im Allgemeinen gibt es für jede nicht negative ganze Zahl $n$ ganze Zahlen $a,b,c,d$ so dass

Joseph-Louis Lagrange hat dies im 18. Jahrhundert bewiesen und wird daher oft als Satz von Lagrange bezeichnet .

Dies wird manchmal in Bezug auf Quaternionen diskutiert - eine Art Zahl, die William Hamilton im 19. Jahrhundert entdeckte und die als wobei sind reelle Zahlen und und sind verschiedene imaginäre Einheiten, die sich nicht kommutativ multiplizieren. Insbesondere wird in Bezug auf das Quadrieren jeder Komponente des Quaternions diskutiert . Diese Größe wird manchmal als Norm oder Quadratnorm oder auch Quadranz bezeichnet . Einige moderne Beweise des Satzes von Lagrange verwenden Quaternionen.

Rudolf Lipschitz studierte Quaternionen mit nur ganzzahligen Komponenten, sogenannte Lipschitz-Quaternionen. Mit der Quadranz können wir uns vorstellen, dass jede Lipschitz-Quaternion einen Freund in den ganzen Zahlen hat. Zum Beispiel kann man sich die Quaternion als der ganzen Zahl . Wenn wir rückwärts gehen, kann man sich jede ganze Zahl als Freund in den Lipschitz-Quaternionen vorstellen.$0+0\textbf{i}+0\textbf{j}+1\textbf{k}$$1=0^2+0^2+0^2+1^2$

Es gibt jedoch ein interessantes Detail des Satzes von Lagrange - die Summe ist nicht eindeutig. Jede Ganzzahl kann verschiedene Sätze von vier Quadraten haben, die summiert werden können, um sie zu erstellen. Zum Beispiel kann die Zahl 1 auf vier Arten mit nicht negativen ganzen Zahlen ausgedrückt werden (betrachten wir für diese Herausforderung nur nicht negative Zahlen):

Die Summanden sind immer Quadrate von 0 oder 1, sie können sich jedoch in verschiedenen Positionen im Ausdruck befinden.

Für diese Herausforderung "sortieren" wir auch unsere Summanden von niedrig nach hoch, um Duplikate zu beseitigen, sodass wir in dieser Übung davon ausgehen können, dass 1 nur eine Möglichkeit hat, als Summe von vier Quadraten dargestellt zu werden:

Ein weiteres Beispiel ist die Zahl 42, die auf vier Arten ausgedrückt werden kann (wiederum nur unter Berücksichtigung von nichtnegativen a, b, c, d und Eliminierung doppelter Komponentenanordnungen).

Was ist, wenn wir uns jede dieser verschiedenen Arten, eine Ganzzahl auszudrücken, als mit einer bestimmten Quaternion assoziiert vorstellen? Dann könnten wir sagen, dass die Zahl 42 mit diesen vier Quaternionen assoziiert ist:

Wenn wir uns die standardmäßige Computergrafikinterpretation einer Quaternion vorstellen, bei der $\textbf{i}$ , $\textbf{j}$ und $\textbf{k}$ Vektoren im dreidimensionalen euklidischen Raum sind und die $x$ , $y$ und $z$ Komponenten der Quaternion dreidimensionale kartesische Koordinaten sind, können wir uns das jeweils vorstellen Eine Ganzzahl kann durch diesen Denkprozess mit einem Satz dreidimensionaler Koordinaten im Raum assoziiert werden. Beispielsweise ist die Zahl 42 den folgenden vier $(x,y,z)$ Koordinaten zugeordnet:

Dies kann als Punktwolke oder als Satz von Punkten im Raum betrachtet werden. Eine interessante Sache an einer Reihe von endlichen Punkten im Raum ist, dass Sie immer einen minimalen Begrenzungsrahmen um sie herum zeichnen können - einen Rahmen, der groß genug ist, um alle Punkte zu passen, aber nicht größer. Wenn Sie sich die Box als eine gewöhnliche Box vorstellen, die an den $x,y,z$ Achsen ausgerichtet ist, wird sie als achsenausgerichtete Begrenzungsbox bezeichnet . Der Begrenzungsrahmen verfügt auch über ein Volumen, das berechnet werden kann, indem Breite, Länge und Höhe ermittelt und miteinander multipliziert werden.

Wir können uns dann das Volumen eines Begrenzungsrahmens für die von unseren Quaternionen gebildeten Punkte vorstellen. Für die ganze Zahl 1 haben wir nach den Kriterien dieser Übung eine Quaternion, deren Quadranz 1, $0+0\textbf{i}+0\textbf{j}+1\textbf{k}$ . Dies ist eine sehr einfache Punktwolke, sie hat nur einen Punkt, daher hat ihre Begrenzungsbox das Volumen 0. Für die Ganzzahl 42 haben wir jedoch vier Quaternionen und somit vier Punkte, um die wir eine Begrenzungsbox zeichnen können. Der minimale Punkt der Box ist $(1,2,4)$ und der maximale Punkt ist $(3,4,6)$ Daraus ergibt sich eine Breite, Länge und Höhe von 2, 2 und 2, was ein Volumen von 8 ergibt.

Nehmen wir an, dass für eine ganze Zahl $n$ das qVolumen das Volumen des achsenausgerichteten Begrenzungsrahmens aller 3D-Punkte ist, die durch Quaternionen gebildet werden, deren Quadranz gleich $n$ , wobei die Komponenten der Quaternion $w+x\textbf{i}+y\textbf{j}+z\textbf{k}$ sind nicht negativ und $w<=x<=y<=z$ .

Erstellen eines Programms oder der Funktion , dass bei einer einzigen nicht negative ganze Zahl $n$ , wird der Ausgang $n$ ‚s qvolume.

Beispiele:

input -> output
0 -> 0
1 -> 0
31 -> 4
32 -> 0
42 -> 8
137 -> 96
1729 -> 10032

Dies ist Code-Golf, die kleinste Anzahl von Bytes gewinnt.

Wolfram Language (Mathematica) , 67-58 Bytes

Volume@BoundingRegion[Rest/@PowersRepresentations[#,4,2]]&

Probieren Sie es online!

                         ...&   Pure function:
PowersRepresentations[#,4,2]    Get the sorted reprs. of # as sums of 4 2nd powers
Rest/@                         Drop the first coordinate of each
BoundingRegion[...]            Find the bounding region, a Cuboid[] or Point[].
                               By default Mathematica finds an axis-aligned cuboid.
Volume                         Find volume; volume of a Point[] is 0.

Gelee , 17 Bytes

Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P

Probieren Sie es online! (ziemlich langsam - mach es schnell genug für alle Testfälle mit einem führenden½ )

Wie?

Żœċ4²S⁼ɗƇ⁸ZḊṢ€I§P - Link: non-negative integer, n    e.g. 27
Ż                 - zero-range                            [0,1,2,...,27]
   4              - literal four                          4
 œċ               - combinations with replacement         [[0,0,0,0],[0,0,0,1],...,[0,0,0,27],[0,0,1,1],[0,0,1,2],...,[27,27,27,27]]
        Ƈ         - filter keep those for which:          e.g.: [0,1,1,5]
       ɗ          -   last three links as a dyad:
    ²             -     square (vectorises)                     [0,1,1,25]
     S            -     sum                                     27
      ⁼  ⁸        -     equal to? chain's left argument, n      1
                  -                                       -> [[0,1,1,5],[0,3,3,3],[1,1,3,4]]
          Z       - transpose                             [[0,0,1],[1,3,1],[1,3,3],[5,3,4]]
           Ḋ      - dequeue                               [[1,3,1],[1,3,3],[5,3,4]]
            Ṣ€    - sort each                             [[1,1,3],[1,3,3],[3,4,5]]
              I   - incremental differences (vectorises)  [[ 0,2 ],[ 2,0 ],[ 1,1 ]]
               §  - sum each                              [2,2,2]
                P - product                               8

Haskell , 132 123 Bytes

z=zipWith
(!)=foldr1.z
h n=[0..n]
f n|p<-[[c,b,a]|a<-h n,b<-h a,c<-h b,d<-h c,a^2+b^2+c^2+d^2==n]=product$z(-)(max!p)$min!p

Probieren Sie es online!

Ziemlich einfache Lösung. Brute Force alle möglichen Lösungen durch Iteration über alle Werte von 0 bis n (viel zu viel, aber kürzer bytecount). Ich gebe den Punkt als Liste aus, damit wir den Zauberoperator von @ Lynn verwenden (!)können. Dieser Operator reduziert jede Dimension mit der Funktion auf der linken Seite, sodass max!peine Liste der Größe 3 zurückgegeben wird, die aus den Maxima in jeder Dimension besteht und min!pfür das Minimum dasselbe tut. Dann finden wir einfach die minimale Größe in jeder Dimension (indem wir den min-Wert vom max mit subtrahieren z(-)) und multiplizieren sie miteinander.

Vielen Dank an @Lynn, der 9 Bytes mit etwas Faltzip-Magie entfernt hat!

Vorschlaghammer 0,2, 12 Bytes

⡌⢎⣟⡊⢘⣚⡏⡨⠍⠁⡇⠨

Verwendung mit Mathematica 11.2 und dieser Version von Vorschlaghammer, die der Herausforderung vorausgeht. Siehe Bearbeitungsverlauf für eine Version, die in Version 0.3 funktioniert, über eine GUI verfügt und einen Mathematica-Ausdruck generiert.

Dadurch wird die Eingabe in den Stapel verschoben und die Befehlssequenz aufgerufen

{intLiteral[4], intLiteral[2], call["PowersRepresentations", 3], call["Thread", 1], call["Rest", 1], call["Thread", 1], call["BoundingRegion", 1], call["Volume", 1]}

Dies entspricht der Auswertung des folgenden Wolfram-Codes, der aus meiner Wolfram Language-Antwort abgeleitet wurde :

Volume[BoundingRegion[Thread@Rest@Thread@PowersRepresentations[#, 4, 2]]]&

Probieren Sie es online!

Python 2 , 138 Bytes

q=lambda n,x=0,*t:[t]*(n==0)if t[3:]else q(n-x*x,x,x,*t)+q(n,x+1,*t+(0,)*(x>n))
p=1
for l in zip(*q(input()))[:3]:p*=max(l)-min(l)
print p

Probieren Sie es online!

Generiert rekursiv die umgekehrt sortierten Quaternionen mit der angegebenen Norm und nimmt dann das Produkt zwischen dem Maximum und dem Minimum aller möglichen Werte in den ersten drei Indizes auf.

itertools hätte vielleicht eine Chance gehabt, wenn es keine lächerlich langen Namen wie itertools.combinations_with_replacement

Python 2 , 161 Bytes

from itertools import*
n=input();p=1
for l in zip(*[t[1:]for t in combinations_with_replacement(range(n+1),4)if sum(x*x for x in t)==n]):p*=max(l)-min(l)
print p

Probieren Sie es online!

Deshalb itertoolsist niemals die Antwort .

JavaScript (ES6),  148  143 Bytes

n=>(r=[[],[],[]]).map(a=>p*=a.length+~a.indexOf(1),(g=(s,k=0,a=[])=>a[3]?s||r.map(r=>r[a.pop()]=p=1):g(s-k*k,k,[...a,++k],k>s||g(s,k,a)))(n))|p

Probieren Sie es online!

Kommentiert

Wir initialisieren ein Array $r$ mit 3 leeren Arrays.

r = [ [], [], [] ]

Für jeden gültigen Wert von $x$Wir werden uns darauf einstellen $1$ der Wert bei $x+1$im ersten Array. Das Gleiche gilt für$y$ und $z$ mit den 2. und 3. Arrays.

Die Abmessungen des Begrenzungsrahmens ergeben sich aus dem Abstand zwischen dem ersten und dem zuletzt eingestellten Eintrag $1$ in diesen Arrays.

Schritt 1

Füllen $r$verwenden wir die rekursive Funktion $g$.

g = (              // g is a recursive function taking:
  s,               // s   = current sum, initially set to the input n
  k = 0,           // k   = next value to be squared
  a = []           // a[] = list of selected values
) =>               //
  a[3] ?           // if we have 4 values in a[]:
    s ||           //   if s is equal to zero (we've found a valid sum of 4 squares):
      r.map(r =>   //     for each array r[] in r[]:
        r[a.pop()] //       pop the last value from a[]
        = p = 1    //       and set the corresponding value in r[] to 1
                   //       (also initialize p to 1 for later use in step 2)
      )            //     end of map()
  :                // else:
    g(             //   do a recursive call:
      s - k * k,   //     subtract k² from s
      k,           //     pass k unchanged
      [...a, ++k], //     increment k and append it to a[]
      k > s ||     //     if k is less than or equal to s:
        g(s, k, a) //       do another recursive call with s and a[] unchanged
    )              //   end of outer recursive call

Schritt 2

Wir können jetzt das Produkt berechnen $p$ der Dimensionen.

r.map(a =>         // for each array a[] in r[]:
  p *=             //   multiply p by:
    a.length +     //     the length of a[]
    ~a.indexOf(1)  //     minus 1, minus the index of the first 1 in a[]
) | p              // end of map(); return p

C # (Visual C # Interactive Compiler) , 229 Byte

a=>{uint b=0,c=~0U,d,e,f=0,g=0,h=0,i=c,j=c,k=c;for(;b*b<=a;b++)for(c=b;c*c<=a;c++)for(d=c;d*d<=a;d++)for(e=d;e*e<=a;e++)if(b*b+c*c+d*d+e*e==a){f=c>f?c:f;g=d>g?d:g;h=e>h?e:h;i=c<i?c:i;j=d<j?d:j;k=e<k?e:k;}return(f-i)*(g-j)*(h-k);}

Probieren Sie es online!

05AB1E , 18 Bytes

Ý4ãʒnOQ}€{ζ¦ε{¥O}P

Probieren Sie es online!

Port of Jonathan Allans Gelee Antwort .

Haskell , 108 Bytes

n%i=sum[maximum[t!!i*b|t<-mapM([0..n]<$f)[0..3],sum(map(^2)t)==n,scanr1 max t==t]|b<-[-1,1]]
f n=n%0*n%1*n%2

Probieren Sie es online! (Zeitüberschreitung bei den größeren Testfällen)

Hier gibt es einige seltsame Optimierungen. Um maximum l-minimum ldie Liste lder Elemente an einer bestimmten Position zu berechnen , ist es im Kontext kürzer, beide Elemente in Maxima umzuwandeln, indem der zweite Ausdruck negiert wird: maximum l+maximum(map((-1)*))loder gleichwertig sum[maximum$map(b*)l||b<-[-1,1]].

Um die drei Dimensionen zu multiplizieren, stellt sich heraus, dass es kürzer ist, nur das Produkt f n=n%0*n%1*n%2zu schreiben, als irgendeine Art von Schleife zu verwenden. Hier n%iist die Differenz zwischen dem min und max der i'ten Koordinatenwerte, die mit der Indizierung extrahiert werden !!i.

Um die gültigen Vierertupel zu generieren, nehmen wir Listen mit vier Zahlen, [0..n]deren Quadrate nin absteigender Reihenfolge addiert werden. Wir überprüfen die Rückwärtssortierung von tmit scanr1 max t==t, um festzustellen , ob das laufende Maximum der Rückwärtssortierung selbst vorliegt , da Haskell keine eingebaute Sortierung ohne kostspieligen Import hat. Wie in meinen Python-Antworten habe ich verschiedene Methoden zum rekursiven Generieren der vier Tupel ausprobiert, aber alle waren länger als diese Brute-Force-Methode zum Generieren und Filtern.