Kwadratura kwadratów
Całkiem poważni matematycy, a ściślej teoretycy liczb, mają następujący poważny problem:
dla jakich n można utworzyć zbiór n różnych liczb całkowitych taki, w którym suma każdej pary liczb będzie kwadratem.
Jest jeszcze dodatkowy warunek: dla danego n szukamy zbioru, w którym największa liczba będzie jak najmniejsza (o ile oczywiście n-liczbowych zbiorów uda się znaleźć więcej niż jeden). I są dwie konkurencje – w pierwszej dopuszcza się liczby ujemne, w drugiej nie. W pierwszej rekordem jest od 42 lat zbiór 6-liczbowy:
{–15863902, 17798783, 21126338, 49064546, 82221218, 447422978}.
W drugiej konkurencji od prawie półwiecza króluje kwintet:
{7442, 28658, 148583, 177458, 763442}.
Nie całkiem poważni teoretycy liczb, czyli np. wyżej nadpisany, mają bliźniaczy „niepoważny” problem: dla jakich n można utworzyć zbiór n różnych liczb naturalnych taki, w którym suma każdych n-1 liczb będzie kwadratem.
Dla n=3 w drugiej konkurencji oba problemy „nakładają się”.
Proszę zatem spróbować znaleźć takie trzy liczby naturalne, że suma każdych dwu z nich będzie kwadratem, zaś suma wszystkich trzech będzie najmniejszą możliwą liczbą.
A może ktoś pokusi się o rozwiązanie „niepoważnego” problemu dla n=4.
Dla zachęty ciekawostka: zbiór trzech liczb, w którym kwadratami są wszystkie możliwe sumy – {41, 80, 320}.
Komentarze
Kiedyś były modne strony, na których programiści prezentowali najbardziej nieczytelne, krótkie programiki, które jednak coś robiły, np. taki:
”=~(‚(?{‚.(‚]])@+}’^’-/@._]’).'”‚.(‚/<[*-_?}{>]}+@}]])@+}@<[*-_?}{>]@^’^’`^=_^<]_[[]+[/,]_/]-/@._]/^=_^<]_[[]+[/,|').',$/})')
Ile znaków ma wasz program dla n=3, który rozwiązuje bieżące zadanie? Można optymalizować i skracać jak się chce, byle tylko policzył. Wydaje mi się, że jest możliwe napisanie kodu krótszego, niż powyższy…
Dla n=3 zbiór minimalny to {6,19,30}.
n=3: 6 19 30 s=55
n=4: 1 2 13 22 s=38
n=5: dla liczb <300 nie znalazłem
Dla n=4 do poprawy (2+13+22=37).
mp
Rozwiązanie dla n=3 -> {6,19,30}
Rozwiązanie dla n=4 -> liczy się… (złożoność jest spora, więc nie oczekuję wyniku w najbliższym czasie)
komputerowo-ciekawy problem jak napisać optymalny obliczeniowo program
Pozdrawiam,
Dla n=4 zbiór minimalny to {1,22,41,58}.
Ja mam 283 znaki w c++ (*)
#include
#include
s(int x){int q=sqrt(x);if(q*q==x);else return 0;}main(){int a,b,c,g,h,S,x;for(S=3;;S++){a=S/3;b=(S-a)/2;c=S-a-b;while(a>0){g=b;h=c;while(a<=g){if(a!=g&&a!=h&&g!=h)if(s(a+g)&&s(a+h)&&s(g+h)){printf("%d,%d,%d",a,g,h);exit(1);}g–;h++;}a–;b++;}}}
Kilku może dałoby się jeszcze pozbyć.
(*) kompilacja z flagami -O0 -fpermissive
Czy istnieją takie trzy polimina, że z każdych dwu z nich można zbudować kwadrat?
Zapewne chodzi o trzy RÓŻNE polimina.
mp
Tak – analogicznie do warunków zadania z liczbami, chodzi o różne polimina (+ uznajmy, że odmienny kształt to też „różność”).
Nie od razu Kraków zbudowano 😉
http://pokazywarka.pl/0zlmvl/
@apartado
Jeśli największy z kwadratów ma bok A, to jedno z polimin musiałoby mieć gabaryty A*A, lecz wtedy nie da się z niego ułożyć drugiego, mniejszego kwadratu.
<pre>*</pre><>*<>
Dla n=3 – Liczby: 6, 19, 30 Suma: 55
Dla n=4 – Liczby:1, 22, 41, 58 Suma: 122
Rozwiązanie kod w Pythonie dla n=3:
import math
def S(x, y): # funkcja sprawdza czy suma liczb jest kwadratem
global v
z=math.sqrt(x+y)
u=math.floor(z)
if (z-u)==0:
v = 1
else: v=0
return v
f=300
for a in range(1,100):
for b in range(1,100):
for c in range(1,100): # przeglądanie kombinacji liczb w zakresie
if (a != b) and (a != c) and (b!=c) : #brak powtórzeń
S(a,b) # sprawdzanie kombinacji liczb
if v == 1:
S(a,c)
if v == 1:
S(b,c)
if v == 1:
e=a+b+c
if e < f : # wybór najmniejszej sumy
f=e
g=a
h=b
i=c
print(g,h,i,f)
kod dla n=4:
import math
def S(x, y, w):
global v
z=math.sqrt(x+y+w)
u=math.floor(z)
if (z-u)==0:
v = 1
else: v=0
return v
f=400
for a in range(1,100):
for b in range(1,100):
for c in range(1,100):
for d in range(1,100):
if (a != b) and (a != c) and (a != d) and (b!=c) and (b != d) and (c != d):
S(a,b,c)
if v == 1:
S(a,b,d)
if v == 1:
S(a,c,d)
if v == 1:
S(b,c,d)
if v==1:
e=a+b+c+d
if e < f :
f=e
g=a
h=b
i=c
j=d
print(g,h,i,j,f)
To nie są najefektywniejsze kody: przebiegając zakresy sprawdzamy kilka razy te same zestawy liczb, kilka zmiennych można wyrzucić, można inaczej sprawdzać czy suma jest kwadratem itp. Ale jest prosty, przejrzysty i działa.
No i wszystkie wcięcia tak istotne w Pythonie wcięło przy wklejaniu w komentarze:-(
Wciąłbym, gdybym wiedział gdzie, ale z pythonów znam tylko dusiciele.
Serio: można zamiast wcięć wstawiać jakieś znaczki, np. podkreślniki (oczywiście tylko tu, w komentarzu)
mp
„Niepoważny” problem dla n=4:
{1, 22, 41, 58}
N=3
{6; 19; 30}
6+19 = 25 = 5*5
6+30 = 36 = 6*6
19+30 = 49 = 7*7
N=4 problem niepoważny
{1; 22; 41; 58}
1+22+41 = 64 = 8*8
1+22+58 = 81 = 9*9
1+41+58 = 100 = 10*10
22+41+58 = 121 = 11*11
Ciekawy problem, klasyczny w formie, prosty w sformułowaniu, stawiający opór. Nie jest to zadanie do jednoznacznego rozwiązania algebraicznego – trzeba trochę poszukiwań i badania liczb jak okazów (fauny, flory lub minerałów).
Ale warto najpierw pobawić się algebraicznie, żeby ułatwić sobie poszukiwania.
n=5 -> {8, 57, 104, 192, 272}
n=6 -> {11, 70, 127, 182, 235, 286}
Wydaje się, że te zbiory istnieją dla wszystkich n bo jest wzór ogólny.
Dla wszystkich n – też tak uważam, ale to hipoteza. Dowodu ani wzoru ogólnego nie znam. Proszę podać (rekurencyjny?).
mp
Jakie jest rozwiązanie minimalne poważnego kwartetu?
Jeśli podobne do królewskiego kwintetu to też zawiera duże liczby, a skoki między pierwiastkami sum są duże i różne (w odróżnieniu od wersji niepoważnych). Pozostają chyba tylko poszukiwania numeryczne…
18530, 38114, 45986, 65570
znalazł Euler (XVIII w.)
mp
Interesujące są różnice pomiędzy kolejnymi elementami zbiorów.
(Dla n=3,n=4,n=5,n=6,…)
A jednak się nie wysłało, jakoś w zeszłym tygodniu,wysłałem dla pewności drugi raz, otrzymując komunikat: „wygląda na to, że przed chwilą wysłałeś taki sam komentarz”. Ale co się odwlecze… wklejam zatem rozwiązanie jeszcze raz (bez zadania „z gwiazdką”).
Jeśli najmniejszą z tych liczb jest p, to kolejna liczba musi być postaci k^2-p, następna n^2-p, i w dodatku k^2+n^2-2p jest kwadratem. Szukamy zatem sum kwadratów jak najmniejszych liczb, tak aby dało się od tego odjąć jak najmniejszą liczbę parzystą, i ta różnica też będzie kwadratem. Na przykład k=9, n=10, k^2+n^2=181 i mamy dość blisko 169, czyli p=12/2 =6, a pozostałe liczby to 81-6 i 100-6, czyli tercet 6, 75, 94. Można jednak zejść jeszcze niżej: k=5, n=6, suma kwadratów jest 61 i niedaleko jest 49. Co daje p znów równe 6, a tercet uzupełniają 19 i 30. Niżej zejść się nie da, np. dla k i n 4 i 6 otrzymamy 52, p byłoby (52-36)/2 = 8, a 16-8 = 8, a więc liczba by się powtórzyła. Dla kolejnych mniejszych sum kwadratów robi się zwyczajnie za ciasno, liczby się powtarzają, np. 2, 2, 7. Tak więc 6, 19, 30, w sumie daje 55.
Z cyklu „heurystyki i algorytmy”:
n=7 ?
n=8 {20,131,240,347,452,555,656,755}
n=9 {8,147,284,419,552,683,812,939,1064}
n=10 ?
n=11 {96,325,552,777,1000,1221,1440,1657,1872,2085,2296}
n=12 {46,309,570,829,1086,1341,1594,1845,2094,2341,2586,2829}
n=13 ?
Zostawiłem trochę miejsca (?) dla dociekliwych.
Może dociekliwi poprawią także n=11 i n=12 (jeśli suma wszystkich liczb ma być najmniejsza).
mp
Wzory dla „niepoważnego” problemu dla n=5 są pod linkiem. Wyprowadzenia na razie nie pokazuje by nie psuć zabawy. Analogicznie wyprowadziłem wzory dla problemu poważnego. Ciekawe czy pomogą coś wartościowego znaleźć ? Jak sprawdzę czy nie zrobiłem byka to zaraz je wrzucę 🙂
http://pokazywarka.pl/h4eozf/
@apartado
Czy chodzi Ci o to, że ciąg różnic w zbiorze szukanym jest taki sam jak w odpowiadającym mu zbiorze kwadratów tylko w odwrotnej kolejności ?
Wyszło mi minimalne rozwiązanie „poważnego” problemu dla n=4.
2, 359, 482, 3362
Jest ono najlepsze zarówno ze względu na najmniejszość największej liczby jak i na minimalność sumy wszystkich wyrazów.
Wzorów na razie nie podaję bo znalezienie ich to sama przyjemność. Pozwalają gigantycznie przyśpieszyć algorytm. Wyszukiwanie w zakresie kwadratów od 1^2 do 500^2 (mowa o zakresie dla zbioru sześciu kwadratów będących sumami wszystkich par szukanego zbioru) zajmuje tylko 1 godzinę i 7 minut.