Kwadratowa jazda
Z ciągu kwadratów (1, 4, 9, 16, 25, 36, 49,…) wybieramy tercety liczb. Kryteria wyboru mogą być różne. Jeśli przyjmiemy, że dwa kwadraty powinny być równe trzeciemu, to wyciągane będą trójki pitagorejskie, a ściślej ich kwadraty, zaczynając od najmniejszej i najbardziej znanej – (3, 4, 5), czyli po ukwadratowieniu (9, 16, 25).
Zaostrzamy kryterium: suma każdej pary kwadratów w tercecie powinna być kwadratem. Obawiam się, że teraz nie uda się wyciągnąć żadnej trójki. Nawet gdyby kwadraty – tylko te wybierane – zastąpić dowolnymi liczbami naturalnymi dodatnimi, sprawa nie byłaby taka prosta, choć oczywiście realizowalna i to na bardzo wiele sposobów, np. (1, 24,120), (2, 23, 98), (3, 22, 78), (4, 21, 60),… itd. (łatwo zauważyć prawidłowość i z automatu dopisywać kolejne tercety, choć daleko tą drogą nie zajedziemy).
Wracamy do kwadratów i ostatecznie modyfikujemy kryterium: z ciągu kwadratów wybieramy liczby i tworzymy z nich ciąg rosnący taki, w którym suma każdych dwóch kolejnych wyrazów będzie kwadratem. Komu uda się najdłużej takim ciągiem jechać i najdalej zajechać?
Komentarze
Ciąg na oko jest nieskończony, więc jest to próba jakości kodu i cierpliwości. Mnie ich starczyło na 46 liczb. Gdyby nagrodą był wpis do Księgi Guinessa, albo lot teslą na Marsa, to bym zostawił program na całą noc, ale chyba i tak nie dotarłbym do 100, gdyż im dalej, tym rzadziej.
Liczby powinny być w trzech kolumnach, ale…
—–
36 435600 243984400
64 480249 268992801
225 853776 388878400
400 1517824 428738436
441 1758276 435974400
784 3125824 437228100
2025 3896676 612661504
3600 6927424 623001600
3969 16208676 640090000
7056 28815424 705699225
12544 41024025 883040656
32400 67240000 890127225
35721 69205761 1092170304
63504 123032464 1228853025
75625 137241225 1721918016
1848742009
Panie Marku, uwielbiam takie zadanka!
Poprzedni algorytm był ad hoc multi-rekurencyjny, czyli siłowy, czyli wykładniczy, czyli musiał się dla dostatecznie dużej liczby załamać. Nie cierpię przemocy, więc mam coś bardziej subtelnego – algorytm O(n) (n, to liczba kwadratów – więc szybciej, niż błyskawica) i to w dwóch wersjach:
1. najmniejsze różnice, czyli najwięcej wyrazów ciągu do pewnej granicy zależnej od bitowości używanej arytmetyki
2. największe różnice, czyli maksymalizacja kwadratu w minimalnej liczbie kroków
Ponieważ obecnie dysponuję tylko 64 bitami, to przedstawiam aktualne rozwiązanie dla wariantu 2:
36
64
225
12544
9828225
24148496748544
czyli liczbę 14-cyfrową.
Mógłbym zapytać o większy wynik Wolframa, ale nie lubię dróg na skróty, więc spróbuję dorobić sobie arytmetykę bez ograniczeń i podać jeszcze lepszy wynik. Nie wiem, co z tego wyjdzie, gdyż właśnie teraz żona powiadamia mnie, że mam 39,6 C gorączki i powinienem iść do łóżka, więc kończę, bo rzeczywiście słabo kontaktuję.
ROZWIĄZANIE
Wybieram dowolną liczbę kwadratową X >=25 (dla mniejszych nie da się utworzyć ciągu)
X będzie pierwszym elementem ciągu
UWAGA! Oto FAKT!
Różnica między dwoma kolejnymi liczbami kwadratowymi
jest zawsze liczbą nieparzystą
Różnica między dwoma dowolnymi liczbami kwadratowymi
jest sumą pewnej liczby kolejnych liczb nieparzystych
PĘTLA
Przedstawiam X jako sumę pewnej liczby kolejnych dodatnich liczb nieparzystych (X = R1+R2+…) – jest to zawsze możliwe 🙂
Dobieram sumę tak, by najmniejsza z sumowanych liczb (R1) spełniła warunki:
– była jak najmniejsza
– stanowiła różnicę między pewnymi dwoma kolejnymi liczbami kwadratowymi Y oraz Z,
– Y > X
Zauważmy, że Y + X = Y + R1 + R2 + … musi być liczbą kwadratową
Liczbę Y dołączam do ciągu i teraz dla niej powtarzam pętlę.
Operację tę można wykonywać w nieskończoność.
Przy wsparciu Python’a stworzyłem program (jako początkujący w tej materii troszeczkę jestem z siebie dumny), który pozwoliłby wskazać dowolnie długi ciąg (przy odpowiednio szybkim procesorze – hehe).
Pozwolę sobie przedstawić nieco krótszy ciąg (29 elementów). Na ten moment na to stać mojego laptopa. 🙂
[36, 64, 225, 400, 441, 784, 2025, 3600, 3969, 7056, 12544, 32400, 35721, 63504, 75625, 435600, 480249, 853776, 1517824, 1758276, 3125824, 3896676, 6927424, 16208676, 28815424, 41024025, 67240000, 69205761, 123032464]
Nie wiem, czy dobrze załapałem problem, w każdym razie można oczywiście próbować, i np. od 1, ani od 4, daleko się nie zajedzie, bo nie ma takich liczb będących kwadratami, których różnica daje 1 lub 4. Trochę lepiej jest w przypadku 9, bo dobieramy 16 i mamy 25, ale to koniec, ponieważ następny kwadrat to już 36, różnica 36-16 = 20>16, czyli stop. Co eliminuje także 16. Wychodząc od 25, mamy 144, i potem szukamy dwóch liczb, których różnica kwadratów dawałaby 144, i znajdujemy (1225 i 1369), co powoduje szukanie dla 1225. Różnice kwadratów (n+1)^2 i n^2 są kolejno liczbami nieparzystymi 3, 5, 7, 9,…, a różnice parzyste (n+2)^2-n^2 liczbami podzielnymi przez 4 (8, 12, 16,…), tak więc znajdzie się para kwadratów o różnicy 1225, po czym mniejsza z tych dwóch liczb wynosi nasze poszukiwania na wyższy poziom, jak jest nieparzysta, to szukamy różnicy liczb różniących się o 1, a jak parzysta, to o 2. I tak możemy się rozbujać do nieskończoności. Podobnie zaczynając od 36, mamy 64, następnie 225, potem 12544, i jesteśmy rozbujani na całego. Następnie idzie 49, 576, etc. No a potem 64 już nie, bo było w ciągu z 36 (tzn, w sumie może być 64, nieskończoność – 1 to dalej jest nieskończoność, ale jest to powiedzmy redundantne). Tak więc 81 kolejny początek. Podejrzewam, że gdzieś tu się nabrałem, ale odważnie wysyłam.
Na najszybciej rosnący ciąg wyprowadziłem taki wzór:
n_nast = ( n_akt^2 – c^2 – 2*n_akt*c )/(2*c) + n_akt
gdzie:
– n_akt na początku dałem 6 (może być inne) i jego kwadrat to 36
– kolejne kwadraty rozwiązania są liczone jako: n_nast^2
– c jest równe albo 1 albo 2 – tylko dla jednej z tych liczb n_nast jest całkowite – trzeba sprawdzić.
A to jest początkowe 11 wyrazów takiego ciągu:
6^2=36
———-
8^2=64
———-
15^2=225
———-
112^2=12544
———-
3135^2=9828225
———-
4914112^2=24148496748544
———-
6037124187135^2=36446868450890434499508225
———-
18223434225445217249754112^2
=
332093554969128125158657133310045015341724460908544
———-
83023388742282031289664283327511253835431115227135^2
=
6892883078252082729362490344393941960005351633831684550151517587543076222807875189964517662640308225
———-
3446441539126041364681245172196970980002675816915842275075758793771538111403937594982258831320154112^2
=
11877959282613476910755268137016407988825857715756623977555153486389712006510347452777080801694105675322240063930720356017265265812670837056005564670336239297903686584987067127408024688424799430508544
———-
11877959282613476910755268137016407988825857715756623977555153486389712006510347452777080801694105675322240063861791525234744438519045933612066145070282722959586841083471891251977262460346047530863367^2
=
141085916719423663057172799516975609340753093016326057924799167991670041970421973404397351313146302192368006558681917369800944542634284331338841072615862710609421434605529872656139869223308754643757448868970507075785265396599542801500473264614399914064220388259616793497853728123500193292877106728119766004268913645813328868816256648864893125964156273339684871503682850100902810222272936412422576689
Widzę powyżej, że wiersze nie są tu zawijane i nie widać całych liczb. Można jednak zaznaczyć fragment i zobaczyć na „Pokaż źródło zaznaczenia”. Ta ostatnia liczba ma 399 cyfr, pokazuję ją „połamaną”:
14108591671942366305717279951697560934075309301632605792479
91679916700419704219734043973513131463021923680065586819173
69800944542634284331338841072615862710609421434605529872656
139869223308754643757448868970507075785265396599542
Inaczej mówiąc: każdej liczbie nieparzystej większej lub równej 3 oraz każdej liczbie podzielnej przez 4 większej lub równej 8, niekoniecznie nawet kwadratom, przyporządkujemy parę liczb takich, że 1) są kwadratami kolejnych liczb naturalnych, bądź dla liczb parzystych, kwadratami liczb różniących się o 2, 2) ich różnica jest równa naszej liczbie. Jeśli tylko mniejsza z tych dwóch liczb jest większa od liczby wyjściowej, to robimy to samo dla niej (na pewno jest albo nieparzysta, albo podzielna przez 4), itd. Zaczynamy od przyporządkowań: 3(1,4), 5(4,9), 7(9, 16), 8(1,9), 9(16, 25), 11(25,36), 12(4,16), 13(36,49), 15(49, 64), 16(9, 25), 17(64,81), 19(81,100), 20(16, 36), 21(100, 121)… i od tego momentu dla każdej liczby mniejsza z pary będzie większa od wyjściowej: 23(121, 144), 24(25,49), itd. Proces możemy ciągnąć do nieskończoności. Wprawdzie np. dla 7 też tak jest, dla 9 też, ale wpadamy w 16, dla której już nie jest, podobnie dla 20. Takie małe uogólnienie jeśli chodzi o pierwszą liczbę w ciągu. Liczby 3, 5, 7, 8, 9, 12, 16, 20 można by jakoś specjalnie nazwać.
Ciągi wydają się być nieskończone.
Najwolniejsza ścieżka wzrostu obcięta do 150 wyrazów to:
1,5
2,12
3,16
4,30
5,40
6,42
7,56
8,90
9,120
10,126
11,168
12,224
13,360
14,378
15,504
16,550
17,1320
18,1386
19,1848
20,1989
21,2652
22,2961
23,3948
24,5264
25,8052
26,9711
27,10198
28,10705
29,14270
30,15502
31,15838
32,16004
33,17022
34,17069
35,17921
36,18667
37,19160
38,19233
39,20199
40,21585
41,23855
42,29021
43,31397
44,31658
45,33238
46,34245
47,35950
48,35967
49,36390
50,37724
51,37946
52,38082
53,38202
54,40115
55,40445
56,42337
57,43032
58,44426
59,44487
60,44710
61,46513
62,46579
63,48078
64,48138
65,48386
66,50814
67,51391
68,51517
69,51606
70,51633
71,52235
72,52411
73,53097
74,53469
75,53471
76,54747
77,54822
78,55872
79,57346
80,57375
81,58510
82,58519
83,58856
84,59592
85,60794
86,61225
87,61851
88,62161
89,62212
90,62865
91,65010
92,65442
93,65726
94,65834
95,65989
96,66299
97,66772
98,68011
99,68042
100,68199
101,68274
102,68380
103,68472
104,69166
105,69301
106,69381
107,69547
108,69654
109,69745
110,69876
111,69878
112,69958
113,70268
114,71055
115,71645
116,72257
117,72850
118,73784
119,74898
120,75075
121,75755
122,76203
123,76543
124,76564
125,76731
126,76837
127,76847
128,77358
129,78123
130,78231
131,78239
132,78587
133,79042
134,79423
135,79560
136,79792
137,79802
138,80399
139,81059
140,81810
141,82210
142,82898
143,83314
144,84034
145,84140
146,84150
147,84709
148,85418
149,85419
150,85630
Oczywiście zamiast kwadratów są ich pierwiastki 🙂
Jak ktoś zrobi komentarz do dawnego wpisu to zostaje on szybko przykryty kolejnymi komentarzami do ostatniego/nich wpisów i szukaj igły w stogu siana. Tak zniknął niedawny komentarz do wpisu Koko. Czy da się coś z tym zrobić ? Może wydłużyć listę NAJNOWSZE KOMENTARZE ?
Jedyny sposób na odświeżenie informacji o nowym komentarzu do starego wpisu to zmiana daty komentarza na bieżący, co też uczyniłem w ramach jednorazowego eksperymentu (Koko).
mp