Od dawna wiadomo, że każdą nieujemną liczbę całkowitą można przepisać jako sumę czterech kwadratowych liczb całkowitych. Na przykład liczbę 1 można wyrazić jako . Lub, ogólnie rzecz biorąc, dla dowolnej nieujemnej liczby całkowitej istnieją liczby całkowite takie, że$0^2+0^2+0^2+1^2$$n$$a,b,c,d$

Joseph-Louis Lagrange udowodnił to w 1700 roku, dlatego często nazywa się to twierdzeniem Lagrange'a .

Czasami jest to omawiane w odniesieniu do czwartorzędów - rodzaju liczby odkrytej przez Williama Hamiltona w XIX wieku, reprezentowanej jako gdzie są liczbami rzeczywistymi, a i to odrębne urojone jednostki, które nie mnożą się przemiennie. W szczególności omawia się to w odniesieniu do kwadratu każdego komponentu czwartorzędu Ta wielkość jest czasem nazywana normą lub normą do kwadratu , a także kwadrantem . Niektóre współczesne dowody twierdzenia Lagrange'a używają czwartorzędów.

Rudolf Lipschitz badał czwartorzędy zawierające wyłącznie składniki całkowite, zwane czwartorzędami Lipschitza. Korzystając z kwadrantu, możemy sobie wyobrazić, że każdy czwartorzęd Lipschitza może mieć przyjaciela w liczbach całkowitych. Na przykład czwartorzędowy można uznać za powiązany z liczbą całkowitą . Ponadto, jeśli cofniemy się, wówczas każdą liczbę całkowitą można uznać za posiadającą przyjaciela w kwaterach Lipschitza.$0+0\textbf{i}+0\textbf{j}+1\textbf{k}$$1=0^2+0^2+0^2+1^2$

Istnieje jednak interesujący szczegół twierdzenia Lagrange'a - podsumowanie nie jest unikalne. Każda liczba całkowita może mieć kilka różnych zestawów czterech kwadratów, które można zsumować, aby ją utworzyć. Na przykład liczbę 1 można wyrazić na 4 sposoby przy użyciu liczb całkowitych nieujemnych (rozważmy tylko nieujemne dla tego wyzwania): 1 = 1 ^ 2 + 0 ^ 2 + 0 ^ 2 + 0 ^ 2

Sumy mają zawsze kwadraty 0 lub 1, ale mogą znajdować się w różnych pozycjach wyrażenia.

W przypadku tego wyzwania „posortujmy” nasze sumy od najniższych do najwyższych, aby wyeliminować duplikaty, abyśmy mogli rozważyć w tym ćwiczeniu, że 1 ma tylko jeden sposób przedstawienia się jako suma czterech kwadratów:

Innym przykładem jest liczba 42, którą można wyrazić na cztery sposoby (ponownie, biorąc pod uwagę tylko nieujemne a, b, c, d i eliminując zduplikowane układy składników)

Co jeśli wyobrażamy sobie, że każdy z tych różnych sposobów wyrażania liczby całkowitej jest powiązany z konkretnym czwartorzędem? Możemy więc powiedzieć, że liczba 42 jest związana z tymi czterema czwartorzędami:

Jeśli wyobrażamy sobie standardową interpretację grafiki komputerowej czwartorzędu, gdzie , i są wektorami w trójwymiarowej przestrzeni euklidesowej , a więc składowe , i czwartorzędu są trójwymiarowymi współrzędnymi kartezjańskimi , wówczas możemy sobie wyobrazić, że każdą liczbę całkowitą, poprzez ten proces myślowy, można powiązać z zestawem trójwymiarowych współrzędnych w przestrzeni. Na przykład liczba 42 jest powiązana z następującymi czterema współrzędnymi :$\textbf{i}$$\textbf{j}$$\textbf{k}$ x y z ( x , y , z ) ( 1 , 4 , 5 ) , ( 1 , 2 , 6 ) , ( 3 , 4 , 4 ) , ( 2 , 3 , 5 )$x$$y$$z$$(x,y,z)$

Można to uznać za chmurę punktów lub zestaw punktów w przestrzeni. Jedną ciekawą rzeczą dotyczącą zestawu skończonych punktów w przestrzeni jest to, że zawsze możesz narysować wokół nich minimalne obwiednię - pole, które jest wystarczająco duże, aby zmieścić wszystkie punkty, ale nie większe. Jeśli wyobrażasz sobie, że to pole jest zwykłym polem wyrównanym do osi , nazywa się to obwiednią wyrównaną do osi . Obwiednia ma również objętość, którą można obliczać, określając jej szerokość, długość i wysokość oraz mnożąc je razem.$x,y,z$

Następnie możemy sobie wyobrazić objętość obwiedni dla punktów utworzonych przez nasze czwartorzędy. Dla liczby całkowitej 1, korzystając z kryteriów tego ćwiczenia, mamy jedną ćwiartkę, której kwadrant wynosi 1, . Jest to bardzo prosta chmura punktów, ma tylko jeden punkt, więc jej obwiednia ma objętość 0. Jednak dla liczby całkowitej 42 mamy cztery ćwiartki, a więc cztery punkty, wokół których możemy narysować obwiednię. Minimalny punkt pudełka to a maksymalny to co daje szerokość, długość i wysokość 2, 2 i 2, co daje objętość 8.$0+0\textbf{i}+0\textbf{j}+1\textbf{k}$$(1,2,4)$$(3,4,6)$

Powiedzmy, że dla liczby całkowitej objętość q jest objętością wyrównanego do osi pola granicznego wszystkich punktów 3D utworzonych przez ćwiartki o ćwiartce równej , gdzie składowe ćwiartki są nieujemne i .$n$$n$$w+x\textbf{i}+y\textbf{j}+z\textbf{k}$$w<=x<=y<=z$

Utwórz program lub funkcję, która, biorąc pod uwagę jedną nieujemną liczbę całkowitą , wyświetli qvolume .$n$$n$

Przykłady:

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

To jest golf golfowy, najmniejsza liczba bajtów wygranych.

Wolfram Language (Mathematica) , 67 58 bajtów

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

Wypróbuj 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.

Galaretka , 17 bajtów

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

Wypróbuj online! (dość wolno - zrób to wystarczająco szybko dla wszystkich przypadków testowych z wiodącym½ )

W jaki sposób?

Żœċ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 bajty

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

Wypróbuj online!

Całkiem proste rozwiązanie. Brute force wszystkie możliwe rozwiązania, iterując wszystkie wartości od 0 do n (o wiele za dużo, ale krócej bajtecount). Wypisuję punkt jako listę, abyśmy mogli użyć magicznego (!)operatora @ Lynn . Ten operator zwija każdy wymiar funkcją po lewej stronie, dlatego max!pzwraca listę rozmiaru 3, która składa się z maksimów wzdłuż każdego wymiaru i min!probi to samo dla minimum. Następnie po prostu znajdujemy minimalny rozmiar w każdym wymiarze (odejmując wartość minimalną od maksymalnej za pomocą z(-)) i mnożymy je razem.

Bardzo dziękuję @Lynn za zdjęcie 9 bajtów za pomocą składanej magii zip!

Młot 0.2, 12 bajtów

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

Używaj z Mathematica 11.2 i tą wersją Sledgehammer, która poprzedza wyzwanie. Zobacz historię edycji dla wersji, która działa w wersji 0.3, która ma GUI i generuje wyrażenie Mathematica.

To wypycha dane wejściowe do stosu i wywołuje sekwencję poleceń

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

co jest równoważne z oceną następującego kodu Wolfram pochodzącego z mojej odpowiedzi Wolfram Language :

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

Wypróbuj online!

Python 2 , 138 bajtów

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

Wypróbuj online!

Rekurencyjnie generuje odwrotnie posortowane czwartorzędy z podaną normą, a następnie przyjmuje iloczyn między maksimum i miną wszystkich możliwych wartości w pierwszych trzech indeksach.

itertools mógłby mieć szansę, gdyby nie używał śmiesznie długich nazwisk takich jak itertools.combinations_with_replacement

Python 2 , 161 bajtów

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

Wypróbuj online!

Dlatego itertoolsnigdy nie jest odpowiedzią .

JavaScript (ES6),  148  143 bajtów

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

Wypróbuj online!

Skomentował

$r$

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

$x$$1$$x+1$$y$$z$

$1$

Krok 1

$r$$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

Krok 2

$p$

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 # (interaktywny kompilator Visual C #) , 229 bajtów

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);}

Wypróbuj online!

05AB1E , 18 bajtów

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

Wypróbuj online!

Port galaretki Jonathana Allana .

Haskell , 108 bajtów

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

Wypróbuj online! (limit czasu dla większych przypadków testowych)

Są tu dziwne optymalizacje. Aby obliczyć maximum l-minimum llistę lelementów w danej pozycji, okazuje się krótszy w kontekście, aby przekonwertować je oba na maksima, negując drugi termin: maximum l+maximum(map((-1)*))llub równoważnie sum[maximum$map(b*)l||b<-[-1,1]].

Aby pomnożyć trzy wymiary, okazuje się, że krótsze jest napisanie produktu f n=n%0*n%1*n%2niż użycie jakiejkolwiek pętli. Tutaj n%ijest różnica między wartością minimalną i maksymalną iwartości współrzędnych, które są wyodrębniane za pomocą indeksowania !!i.

Aby wygenerować poprawne cztery krotki, bierzemy listy czterech liczb, z [0..n]których kwadraty sumują się ni maleją. Sprawdzamy odwrotność sortowania za tpomocą scanr1 max t==t, która sprawdza , czy maksimum biegu wstecznego jest samo w sobie, ponieważ Haskell nie ma wbudowanego sortowania bez kosztownego importu. Próbowałem różnych sposobów rekurencyjnego generowania czterech krotek, tak jak w moich odpowiedziach w języku Python, ale wszystkie były dłuższe niż ten sposób generowania i filtrowania brutalnej siły.