Zadanie polega na wyliczeniu rozwiązań w dziedzinie dodatnich całkowitych za pomocą peceta domowego:
a^4+b^4+c^4=d^4
dla liczb do miliarda przynajmniej: d < 10^9.
Ktoś da radę to zrobić?
Idąc z tym na piechotę wyjdzie chyba 10^27 sprawdzeń, co trwałoby tysiące lat na pececie, zatem taka metoda odpada.
Trzeba to jakoś zredukować do 10^9 przynajmniej, czekam na pomysły.
Zobacz tutaj:
https://mathworld.wolfram.com/DiophantineEquation4thPowers.html
tamże sporo odnośników do badań.
Jak również:
https://www.ams.org/journals/mcom/1988-51-184/S0025-5718-1988-0930224-9/S0025-5718-1988-0930224-9.pdf
Ogólnie wyszukuj na hasła: "diofante equation 4 powers", "euler quadric conjecture"; być może są jakieś prace ograniczające przestrzeń. @szatkus, z powyższego wynika, że nie istnieje rozwiązanie dla D <= 10000.
być może są jakieś prace ograniczające przestrzeń
Można zacząć od tego → https://www.ams.org/journals/mcom/1988-51-184/S0025-5718-1988-0930224-9/S0025-5718-1988-0930224-9.pdf ← a potem się pobawić krzywymi eliptycznymi.
Nie zauważam żadnej formuły w tym pdf:
ile jest rozwiązań w granicach do miliarda, biliona?
Mam pomysł jak to podejść prymitywnie numerycznie, ale chyba jest zbytnio optymistyczny aby był poprawny,
bo redukuje problem aż kwadratowo, co znaczyłoby że wystarczy zaledwie 1 miliard iteracji, aby wyliczyć wszystkie te czwórki do miliarda: d < 10^9
ile jest rozwiązań w granicach do miliarda, biliona?
Nie wiem czy ktokolwiek będzie w stanie Ci na to pytanie odpowiedzieć… W tamtym PDF-ie masz algorytm znajdowania rozwiązań, który generuje nieskończenie wiele wyników, ale nie są to wszystkie możliwe wyniki.
Nie zauważam żadnej formuły w tym pdf:
ile jest rozwiązań w granicach do miliarda, biliona?
Niestety/stety :) temat nie jest trywialny, i musisz przejrzeć więcej niż jedną publikację.
Nie strasz mnie!
Może podam mój trop, który należy obalić, co chyba będzie niełatwe raczej.
Proponuję prymitywny schemat obliczeń:
biorę czwórki kwadratów, zamiast do 4, co znaczy produkuję od razu:
a^2 + b^2 + c^2 = d^2
na takie czwórki jest już znany wzór explicite, zatem jadę tym wzorem - bez zbędnych iteracji!
podczas jazdy sprawdzam po drodze czy: d jest kwadratem: d = s^2, i gdy jest wtedy sprawdzam podobnie pozostałe: a = p^2, b = q^2, c = r^2.
i gdy trafię wtedy mam wynik! nie muszę nawet wyliczać tych ogromnych liczb: a^4, bo warunek jest pewny:
a^2 + b^2 + c^2 = d^2; (a,b,c,d) = (p^2, q^2, r^2, s^2), więc mam automatycznie żądane 4 liczby pgrs: p^4 + q^4 + r^4 = s^4
Formuła na 4-ki Pitagorasa:
https://en.wikipedia.org/wiki/Pythagorean_quadruple
przy okazji widać że: d i a muszą być nieparzyste, b i c - parzyste (pomijając skalowanie).
Nie strasz mnie!
Ciśniesz się w coś, co wygląda jak materiał na publikację naukową… Więc tak, nie będzie to trywialne.
biorę czwórki kwadratów, zamiast do 4, co znaczy produkuję od razu:
a^2 + b^2 + c^2 = d^2
Mam już pewne wątpliwości, co do tego kroku; czy można aż tak uprościć?
Mam już pewne wątpliwości, co do tego kroku; czy można aż tak uprościć?
Nie można. Zauważ, że:
,
ale:
,
Błędne rozumowanie.
Jest pewne że szukane czwórki są zarazem kwadratami - zgadza się?
a^2^2 = a^4.
zatem wystarczy iterować kwadraty wg schematu: a^2 + b^2 + c^2 = d^2,
co jest znacznie szybsze (bo to pójdzie kwadratowo!) od ślepej drogi po wszystkich całkowitych!
Szukamy p^4 + ... , zatem robimy jedynie test po drodze: a = kwadrat i b = kwadrat i to samo c, d.
Powinno pójść w czasie sqrt(n), bo ten schemat jedzie przecież kwadratami, a nie liniowo:
d = m^2+n^2+p^2+q^2.
Wystarczy porównać moje sugestie z prostszą wersją - dla relacji trójek: a^2+b^2 = c^2.
Idąc z tym na piechotę musimy przelecieć kolejno: a, b = 1,2,3 ... co daje n^2 kombinacji.
Zatem do miliarda wyjdzie 10^18, co jest niemożliwe do przerobienia w rozsądnym czasie na komputerku!
Tylko że co za problem przyspieszyć to - kwadratowo!, mając gotowe wzory:
a = m^2-n^2; b = 2mb; c = m^2 + n^2;
to z mety gwarantuje zadaną relację, no i zasuwa kwadratowo - nie jest tak?
Ile jest rozwiązań do miliarda w tym przypadku: c < 10^9 ?
Analogicznie jest z wersją czwórkową: a^2+b^2 + c^2 = d^2;
a troszkę dalej mamy już: a^4+b^4+c^4 = d^4
co jest przecież podzbiorem: a^2+b^2+c^2 = d^2, w którym jedynie a,b,c,d są kwadratami!
Mamy zadanie wstępne (na przetarcie) - wyliczyć liczbę zwyczajnych trójek Pitagorasa:
a^2+b^2=c^2
do 1 miliarda, czyli: c < 10^9.
Ja to z matmy cienki jestem. Ale na chłopski rozum wydaje mi się że ciebie nie interesuje rozwiązanie tego problemu w sposób matematyczny tylko w sposób "informatyczny". Czyli możesz robić jakieś dziwne tricki w programie które ograniczą Ci ilość możliwych kombinacji dla komputera. Bo jak koledzy wcześniej zauważyli to raczej temat na prace.
Dla uproszczenia będę omawiał dla d = 10.
Założyłem że a != b != c ale nie umiem tego udowodnić.
Pytanie czy są inne tricki które by Ci uprościły wyliczenia? Mówiłeś coś o parzystych i nie parzystych liczbach. Może jakieś sumy z par i przeszukiwanie indeksu za pomocą standardowych metod jak b-tree? Z tego co pamiętam B-Tree dla znalezienia czegoś w drzewie składającego się z miliona elementów potrzebuje 32 sprawdzeń (może to jest tańsze dla procesora niż liczenie wszystkiego ciągle parę razy bez cache?
Dla d = 1.000.000.000 wychodzi mi coś około 7.700.000.000 kombinacji a to wydaje się realne już do policzenia w skończonym czasie.
Do policzenia 1.000.000.000 potęg 4 stopnia na moim kompie potrzeba około 62 sekundy w języku do tego nie przygotowanym. Czyli po ~70 sekundach i bardzo dużej ilości pamięci (około 8 GB) masz zbudowany cache :P
Edit.
Zauważyłem jeszcze że
Także dla C<= 7 nie może istnieć rozwiązanie bo 7^4 stanowi jedynie 24% całej liczby więc nawet jeżeli zrobimy 24% * 3 < 100%. Co za tym idzie zostaje nam jedno rozwiązanie które możemy wykluczyć z powodu wcześniejszych punktów. Zmierzam do tego że naprawdę nie musisz wykonywać tylu obliczeń na ile wskazuje czysta matematyka.
Marne sugestie, ale kombinuj dalej.
I pamiętaj że tu chodzi o dość duże liczby, typu: miliard ^ 4 = 10^36.
a^4 + a^4 + a^4 = 3a^4 <> d^4, w dziedzinie całkowitych, zatem te liczby na pewno nie mogą być równe.
a^4 + a^4 + c^4 = 2a^4 + c^4 = d^4, też odpada: teza bez dowodu, bo to jest banał (Pitagoras się kłania).
zatem te liczby muszą być różne.
Wielkość liczb dla komputera NIE MA znaczenia bo procesor ma specjalną jednostkę do obliczeń takich rzeczy. A jeśli NIE MA to i tak operuje na wszystkich bitach liczby. Jeszcze raz to powtórze że mam wrażenie że ty szukasz rozwiązania matematycznego, a nie kodu.
Gdzie moje rozumowanie jest błędne? bo ja jakoś nie dostrzegam błędu. To że masz liczby całkowite nic nie zmienia bo możesz operować tylko na naturalnych z racji potęgowania przez 4.
Jeśli dobrze myśle to złe forum wybrałeś do pomocy.
@enedil:
Pozwolę sobie odpowiedzieć w poście bo się w komentarzu nie zmieściłem.
To teraz ja znów nie zgodze się z twoim twierdzeniem. Bo liczba z zerem na końcu podniesiona do potęgi n-tej zawsze daje na końcu zero. Co oznacza że szukamy zbioru 3 liczb gdzie suma ich wyniku potęgowania daje na końcu zero. Innymi słowy to nie jest dowolny zbiór liczb bo jest silna korelacja pomiędzy liczbami
Założenie: d = 10^dowolnej liczby
np:
2^4 => 16
22^4 => 234.256
Jakiej liczby byśmy nie wzięli to jeżeli na jej końcu będzie cyfra 2 to podniesiona do 4 potęgi da nam ostatnią cyfrę w wyniku "6". Wiedząc to zbiory liczb znów ulegają skróceniu. bo by uzyskać 0 na końcu można zwiać tylko cyfry:
0^4 => 0
1^4 => 1
2^4 => 16
3^4 => 81
4^4 => 256
5^4 => 625
7^4 => 2.401
8^4 => 4.096
9^4 => 6.561
I teraz jak przyjrzysz się na końcówki liczb to by uzyskać "0" na końcu możliwy jest tylko 2 zbiory biorąc pod uwagę że autor szuka sumy 3 cyfr. Tymi zbiorami są cyfry (c = 5, b = 5, a = 0) oraz.(c = 0, b = 0, a = 0) Każda inna kombinacja nie da na końcu 0 po zsumowaniu co za tym idzie nie może być równa d.
Uzbrojeni w taką wiedzę z poziomu 100% liczb początkowych wykorzystywanych do wygenerowania wszystkich sekwencji schodzimy do 20% liczb do tego potrzebnych. Dodając do tego właściwość że suma liczb nie może być mniejsza niż 50% podstawy liczby docelowej znów ucinamy zbiór do 10% całości. A jeszcze jak powiemy sobie że najwyższy składnik to 85% liczby bazowej to około 3% utniemy zbioru liczb.
W efekcie zakładając że dla d = 100 dało by się wygenerować zbiór 3 liczb to musimy przebadać jedynie 7% kombinacji wszystkie inne odpadają. dla np 10 przebadać musielibyśmy jedynie zbiór
5^4 + 5^4 + 0^4, co i tak NIE MA sensu bo 0^4 to 0% liczby, a 5^4 to zaledwie 6% liczby.
Dla następujących d wygląda to tak:
d = 10 => z 120
d = 100 => 615 z 161700
d = 1.000 => 661.650 z 166.167.000
d = 10.000 => 666.166.500 z 166.616.670.000
Ilość rośnie lawinowo ale jest możliwa do obróbki przez komputer jeśli dorzucimy jeszcze inne twierdzenia które same w sobie wiele nie dają ale w połączeniu mocno zmniejszają ilość kombinacji. Tak mi się wydaje :D
@YourFrog2: No to ja pozwolę się nie zgodzić, bo d nie ma być równe 10^9, tylko ma być mniejsze niż 10^9, więc wszystkie Twoje założenia o postaci d mogą być wyrzucone w błoto. Ale nawet zakładając, że tak jest, to 6% to zdecydowanie za dużo, bo to jest wtedy koło
10^9 * 10*9 * 0.07 ~ 10^17, czyli tak z 6.5 rzędów wielkości za dużo (zakładając, że mamy strategię - wybór a, wybór b, c = ((10^9)^4 - (a^4 + b^4)) ^ (1/4) - ten pierwiastek czwartego stopnia zajmuje też raczej z kilkadziesiąt instrukcji).
@YourFrog2: redukcja, którą proponujesz jest bezużyteczna, bo to idzie nadal liniowo.
Dlatego ja proponuję schemat kwadratowy wyliczania tych liczb!
Bo tylko wtedy będzie osiągalny ten miliard w sensownym czasie:
sqrt(10^9) = 31000,
idąc schematem po kwadratach, który opiera się na dwóch parametrach: m i n,
zatem to daje kwadrat kombinacji, czyli 10^9 operacji, co jest już realne do wyprucia na pececie!
Ty proponujesz redukcję 100 krotną - do 1%?
To jest nic.
Popatrz sobie jaka jest redukcja wg metody kwadratowej: 10^9/10^27 = 10^-18 = ile to jest procentów? zero.
Wracając do meritum, po drodze otrzymałem mały problem, w postaci:
p^2 + q^2 = 2mn
mamy dane m i n, i należy wyznaczyć p i q, ponieważ one są potrzebne do dalszych wyliczeń.
Ma ktoś pomysł jak to zrobić sprytne i szybko?
Ko. Widzę brak zainteresowania, zatem można usunąć ten temat.
Pozostawiam jako zadanie wyliczenie wszystkich: c - przekątnych z trójek Pitagorasa do miliarda:
c^2 = a^2 + b^2
ile jest przekątnych: c < 10^9 ?
A jeśli dam radę wyliczyć te czwórki do 4, wtedy podam wyniki.
Do zobaczenia.
@Bet: Ty też się zwodzisz, użycie czwórek pitagorasa wcale nie daje przyspieszenia, zamiast liczb a, b, c, d (efektywnie 3 zmienne), masz m, n, p, q (4 zmienne), z czego każda z tych 7 liczb może być rzędu 1e9. Czyli zamiast przyspieszyć, jeszcze spowolniłeś, i to 1e9-cio krotnie.
Nie. Gotowe wzory dają zawsze liniową szybkość, bo szybciej nie można tego produkować - to jest oczywiste!
Sekwencyjne szukanie kwadratów: a^2+b^2 = c^2, wymaga aż n^2 operacji, bo tyle jest kombinacji par a i b < n.
a^4 + b^4 + c^4 = d^4 - tu pójdzie n^3
ale po wykorzystaniu wzorów na te czwórki Pitagorasa to będzie już n^1.5 chyba:
sekwencja: a, b, c: nnn = n^3,
ale gdy pojedziemy tym kwadratowo wtedy będzie n^0.5 * n^0.5 * n^05 = n^1.5;
a w sumie to wyjdzie n^2, bo tam są 4 parametry: m,n,p,q
w najgorszym przypadku, ale spodziewam się tu pełnej redukcji do n
wystarczy zredukować te 4 parametry do dwóch:
M = m^2+n^2, i P = p^2+q^2
a patrząc na te wzory jest to bardzo prawdopodobne, i będziemy zasuwać z tym liniowo: miliard^1 = miliard!
a^2 = m^2+n^2 - (p^2+q^2) = M - P
ale:
d^2 = m^2+n^2 + (p^2+q^2) = M + P
jak widać ładnie się redukuje: (ad)^2 = M^2 - P^2, zatem to jest prosty Pitagoras!
pozostałe: b^2 i c^2 należy podobnie rozłożyć, a wtedy będzie rakieta!
Nie wystarczy redukcja do twoich P i M, bo ze wzorów z wikipedii, to by znaczyło że
(M - P) + b^2 + c^2 = (M + P)
ma zawsze dokładnie jedno rozwiązanie (gdzie zmiennie to b oraz c) a to nie może być prawda, czego uczy nas np. liczba 1729, rozkładalna na 2 sposoby na sumę kwadratów.
I wcale liniowo nie będziesz zasuwać, bo masz dwa parametry, P i M, z których każdy może być wielkości 10^9 (to zakładając że ignorujesz co napisałem powyżej o tym, że tamto równanie wcale nie ustala wszystkich parametrów).
Zresztą, chyba nie masz ochoty się niczego z wątku nauczyć, więc z mojej strony, koniec tematu.
To jest chyba zbyt łatwe dla mnie!
Biorąc dwa pozostałe wzory - na b i c, otrzymamy tam znowu piękną redukcję w M i P!
b^2 = 2mq + 2np
c^2 = 2nq - 2mp
co rozwiązując, otrzymujemy:
p = (nb^2 - mc^2)/2(m^2+n^2), q = (mb^2 + nc^2)/2(m^2+n^2);
(przy okazji widać tu wyraźnie jakiś przecieki z algebry liczb zespolonych!)
a teraz sprawdźmy co z tego wyjdzie - suma kwadratów:
p^2 + q^2 = (b^4+c^4)/4(m^2+n^2),
czyli to faktycznie pięknie się rozkłada: 4MP = b^4+c^4;
no i jednak mamy teraz tylko dwa parametry: M i P, zamiast czterech: m,n, p i q !
Ten chwyt z M i P, niewiele daje.
Ostateczny algorytm wyglądałby następująco:
jedziemy po m i n, m > n, i uwzględniając że jedno z nich musi być parzyste, np. m = 5, wtedy n = 2; m = 6, wtedy n = 1,3,5, itd.
szukamy p i q, poprzez relację: p^2 + q^2 = 2mn, co wymaga trochę obliczeń, niestety.
sprawdzamy te dwa wzory na b, i c, znaczy:
2(mq - np) oraz 2(nq + mp) - oba muszą być kwadratami: b^2 i c^2
co chyba można załatwić sprytniej, ponieważ te dwa wzory to zwyczajne mnożenie zespolonych:
z = 2(m,n)(p,q) = (b^2,c^2), |z|^2 = 4|(m,n)(p,q)|^2 = 4(m^2+n^2)(p^2+q^2) = 4MP = |b^2,c^2|^2
p^2+q^2 = 2mn, więc być może uda się zupełnie wyeliminować p i q:
4(m^2+n^2)(p^2+q^2) = 4(m^2+n^2)2mn = ...
i to chyba tyle.
Złożoność tego schematu jest chyba niedużo większa od n, góra n^1.5, zatem można próbować wyliczyć wszystkie czwórki do n=miliard w czasie kilku godzin.
Można także spróbować poćwiczyć i wyprodukować: m,n,p,q, mając dane a,b,c,d;
95800^4 + 217519^4 + 414560^4 = 422481^4
biorąc pod uwagę: a = m-n, d = m+n, co dla danych:
a = 217519, d = 422481,
daje zabawne liczby:
m = (422481 + 217519) / 2 = 320000, bardzo ciekawe,
n = (422481 - 217519) / 2 = 102481; ta jest pierwsza - niepodzielna
zatem:
p^2 + q^2 = 2mn = 2x320000x102481
p, q = ? tu jest chyba z 10 możliwości!
Coś mi to wygląda na przesadnie przeładowane - za dużo tych parametrów.
Ale chcesz obliczyć numerycznie czy algebraicznie? Rozwiązanie algebraiczne jak najbardziej istnieje:
https://en.wikipedia.org/wiki/Quartic_equation
Tam masz wyprowadzenie wzoru na pierwiastki. Temat nie jest prosty i należy się zastanowić, czy wyliczanie ze wzorów ma sens.
I tak btw nie pamiętam teraz jakie to było twierdzenie, ale udowodnione jest, że w ogólnym przypadku nie da się wyprowadzić wzorów na pierwiastki wielomianu stopnia 5 i wyższych.
