31

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$

n = {za}^{2)} + b^{2)} + {do}^{2)} + {re}^{2)}

$n = a^2+b^2+c^2+d^2$

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.

w + x ja + y jot + z k

$w+x\textbf{i}+y\textbf{j}+z\textbf{k}$

w, x, y, z

$w,x,y,z$

i, j

$\textbf{i}, \textbf{j}$

k

$\textbf{k}$

w^{2)} + x^{2)} + y^{2)} + z^{2)}

$w^2+x^2+y^2+z^2$

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 = 0^{2)} + 0^{2)} + 0^{2)} + 1^{2)}

$1=0^2+0^2+0^2+1^2$

1 = 0^{2)} + 0^{2)} + 1^{2)} + 0^{2)}

$1=0^2+0^2+1^2+0^2$

1 = 0^{2)} + 1^{2)} + 0^{2)} + 0^{2)}

$1=0^2+1^2+0^2+0^2$

1 = 1^{2)} + 0^{2)} + 0^{2)} + 0^{2)}

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

1 = 0^{2)} + 0^{2)} + 0^{2)} + 1^{2)}

$1=0^2+0^2+0^2+1^2$

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)

42 = 0^{2)} + 1^{2)} + 4^{2)} + 5^{2)}

$42=0^2+1^2+4^2+5^2$

42 = 1^{2)} + 1^{2)} + {2)}^{2)} + 6^{2)}

$42=1^2+1^2+2^2+6^2$

42 = 1^{2)} + {3)}^{2)} + 4^{2)} + 4^{2)}

$42=1^2+3^2+4^2+4^2$

42 = {2)}^{2)} + {2)}^{2)} + {3)}^{2)} + 5^{2)}

$42=2^2+2^2+3^2+5^2$

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:

0 + 1 ja + 4 jot + 5 k

$0+1\textbf{i}+4\textbf{j}+5\textbf{k}$

1 + 1 ja + 2) jot + 6 k

$1+1\textbf{i}+2\textbf{j}+6\textbf{k}$

1 + 3) ja + 4 jot + 4 k

$1+3\textbf{i}+4\textbf{j}+4\textbf{k}$

2) + 2) ja + 3) jot + 5 k

$2+2\textbf{i}+3\textbf{j}+5\textbf{k}$

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)

$(1,4,5),(1,2,6),(3,4,4),(2,3,5)$

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.

code-golf complex-numbers

— Don Bright
źródło

co muszę dodać? Chciałem wskazać, że wygra najmniejsza liczba bajtów

— don

3

Zapomniałeś tagu code-golf, pomogłem Ci go dodać

— Embodiment of Ignorance

1

To miłe wyzwanie, ale byłoby jeszcze lepiej IMHO, gdyby było nieco mniej gadatliwe. Uważaj też na nieistotne linki (nie mówię, że wszystkie twoje linki są nieistotne, ale tylko kilka z nich naprawdę dostarcza istotnych informacji na temat wyzwania, podczas gdy inne tylko rozpraszają uwagę).

— Arnauld

1

Tak, ale dlaczego brać tylko i, j, k jako przestrzeń 3D, ale nie 4D?

— tsh

1

@ ich, ponieważ czwartorzędy niekoniecznie reprezentują 4-wymiarową przestrzeń euklidesową. Hamilton odkrył je, szukając sposobu pracy z przestrzenią trójwymiarową. Byłoby możliwe wykonanie wersji 4d, ale zastanawiałem się nad ich wykorzystaniem w przestrzeni 3D, kiedy zadałem pytanie

— don bright

13

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.

— lirtosiast
źródło

4

wow, nie miałem pojęcia, że coś takiego jak PowersRepresentations będzie wbudowane w język. faktycznie myślałem o podjęciu wyzwania, aby pokazać różne sposoby zsumowania liczby całkowitej jako czterech kwadratów, ale cieszę się, że tego nie zrobiłem.

— don jasny

4

Lol, Mathematica ma nawet wbudowane narzędzie do określania kóz na obrazie , więc posiadanie wbudowanego narzędzia do tego naprawdę mnie nie dziwi. xD

— Kevin Cruijssen

8

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

— Jonathan Allan
źródło

6

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!

— użytkownik 1472751
źródło

1

Ogoliłem kilka bajtów, rezygnując z transpozycji na rzecz jakiejś zipWithlogiki. 123 bajty

— Lynn

5

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!

— lirtosiast
źródło

czy to wymaga matematyki do przetestowania?

— don jasny

@don bright Tak, repozytorium zawiera instrukcje. To praca w toku, więc jeszcze niezbyt przyjazna dla użytkownika. Po uruchomieniu setup.wls możesz przetestować za pomocą wolframscript lub Interactive_app.wls.

— lirtosiast

2

@Downgoat Tak. Planuję wdrożyć bibliotekę do gry w golfa, ale obecnie dekompresuje się ona do zwykłej matematyki.

— lirtosiast

2

@pipe Starsza wersja powinna działać (teraz, gdy o niej myślę, kod jest dokładnie taki sam na jednej starszej wersji), ale musiałbym ją pobrać i uruchomić ponownie. (Od tego czasu zmiany polegały głównie na pisaniu GUI i refaktoryzacji kodu bez większych zmian w funkcjonalności.) Ponieważ ta odpowiedź jest najkrótsza, ważne jest, aby udowodnić kwalifikowalność, więc zrobię to jutro rano.

— lirtosiast

1

czy ktoś może to uruchomić? Chciałbym sprawdzić, czy to działa, zanim pokażę mu stary znacznik wyboru.

— don jasny

4

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ą .

— xnor
źródło

3

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

— Arnauld
źródło

2

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!

— Wcielenie ignorancji
źródło

2

05AB1E , 18 bajtów

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

Wypróbuj online!

Port galaretki Jonathana Allana .

— Ponury
źródło

1

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.

— xnor
źródło

Qvolume liczby całkowitej

Wolfram Language (Mathematica) , 67 58 bajtów

Galaretka , 17 bajtów

W jaki sposób?

Haskell , 132 123 bajty

Młot 0.2, 12 bajtów

Python 2 , 138 bajtów

JavaScript (ES6), 148 143 bajtów

Skomentował

Krok 1

Krok 2

C # (interaktywny kompilator Visual C #) , 229 bajtów

05AB1E , 18 bajtów

Haskell , 108 bajtów