Po 60 latach rozwiązano równanie x3+y3+z3=33

6 minut temu, KopalniaWiedzy.pl napisał:

Zatem z zakresu od k=1 po k=100 pozostała jeszcze jedna nierozwiązana liczba – 42.

Przypadek? Nie sądzę.

Na pierwszy rzut oka zadanie nie wydaje się bardzo złożone obliczeniowo, ale po chwili liczenia, przestrzeń ma 8*10⁴⁸ punktów. Nie wróżę sukcesów brute force'om

1 godzinę temu, Jajcenty napisał:

Przypadek? Nie sądzę.

1 godzinę temu, Jajcenty napisał:

Nie wróżę sukcesów brute force'om

Niby ciężko ale spróbować zawsze warto, ba nawet "raz"| spróbuję (nie znałem tej klasy problemów)

[edit]

Ciekawe czy da się chociaż "trochę" to jakoś zoptymalizować

Da się brute tylko trochę inaczej. Zauważ, że tutaj sprowadzone jest to do +--, pierw dwie duże liczby, o przeciwnym znaku (pierwsza większa), a trzecią zbliżasz się do wyniku. Można sobie wygenerować kilka milionów takich liczb, wybrać obiecujących kandydatów (biorąc pod uwagę zasady podnoszenia do sześcianu) i następnie je korygować. Szukanie wyniku metodą gradientową.

27 minut temu, wilk napisał:

Zauważ, że tutaj sprowadzone jest to do +--, pierw dwie duże liczby, o przeciwnym znaku (

hm..w zasadzie to mamy tu zawsze kombinacje.

dwie ujemne jedna dodatnia

dwie dodatnie jedna ujemna

a no tak ok, czyli 2 o przeciwnym znaku i trzecia o dowolnym  

27 minut temu, wilk napisał:

Można sobie wygenerować kilka milionów takich liczb, wybrać obiecujących kandydatów (biorąc pod uwagę zasady podnoszenia do sześcianu)

ok, tutaj muszę doczytać, bo nie znam na ten moment zasad które by mi pomogły

27 minut temu, wilk napisał:

Szukanie wyniku metodą gradientową.

Rozumiem, ale nie jestem takim optymistą, 

(z resztą chyba tak będę liczył  ) 

Dziś wieczorem przysiądę, pomyślę i jak dobrze pójdzie to jutro odpalę na parę godzin kompa z liczeniem na sępa, że trafię, nie trafię to cóż...kto nie próbuje. ten nigdy nie trafi

38 minut temu, Afordancja napisał:

Dziś wieczorem przysiądę, pomyślę i jak dobrze pójdzie to jutro odpalę na parę godzin kompa z liczeniem na sępa, że trafię, nie trafię to cóż...kto nie próbuje. ten nigdy nie trafi

Zastanów się (ja się zastanawiam) jak wykorzystać informację, że w przedziale [-10¹⁶ ; 10¹⁶] NIE MA rozwiązania. To eliminuje z obliczeń sporo punktów. Powinno się dać to jakoś wykorzystać.

Godzinę temu, wilk napisał:

Szukanie wyniku metodą gradientową.

Moja druga myśl. Korzystając z ciągłości n³ można te minima dość szybko znajdować.

Godzinę temu, Jajcenty napisał:

Korzystając z ciągłości n³ można te minima dość szybko znajdować.

A ja ciągle jestem bardzo sceptyczny jeśli chodzi o Twój optymizm

Będziemy zazwyczaj po prostu "przeskakiwać" ten prawidłowy wynik. Tak jak w zwykłej faktoryzacji 

Godzinę temu, Jajcenty napisał:

Zastanów się (ja się zastanawiam) jak wykorzystać informację, że w przedziale [-10¹⁶ ; 10¹⁶] NIE MA rozwiązania. To eliminuje z obliczeń sporo punktów. Powinno się dać to jakoś wykorzystać.

Tak to jedyna dająca nadzieję wiadomość. Jednak wykluczone jest to, że wszystkie 3 są w tym zakresie, ale 2 już mogą być. Ułatwia ale nie aż tak bardzo jak by się mogło wydawać.

No nic wieczorem zrobię sobie burzę mózgu

[edit]

Wiele nie wydumałem na razie, po za tym, że co najmniej 2 liczby z trzech, muszą mieć resztę z dzielenia przez 3 wynoszącą 2. Idę dalej dumać

Jak rozwiążecie, to pamiętajcie, żeby nagrodą i fejmem podzielić się ze źródłem inspiracji.

Ja również nie znałem tej klasy problemów.

Challenge accepted

Mariusz, podzielę się jak napiszecie artykuł o tego typu ciekawostkach matematyczo-algorytmicznych

Przecież nie ważne ile jak na "plus" a ile na "minus"  - po prostu wystarczy sztywne założenie 2+ i 1- i obliczać moduł.
Dzięki temu nie trzeba się bawić ze zmienianymi działaniami. Radykalnie się zmniejsza ilość kombinacji. Potem wystarczy przestawić.

Dokładnie, a wydaje mi się, że jest jeszcze jednak optymalizacja... musze sprawdzić

23 godziny temu, KopalniaWiedzy.pl napisał:

Zatem z zakresu od k=1 po k=100

Zatem z zakresu od k=1 do k=50 pozostaje jeszcze jedna nierozwiązana liczba - 42. Przypadek?

Zatem z zakresu od k=1 do k=60 pozostaje jeszcze jedna nierozwiązana liczba - 42. Przypadek?

Zatem z zakresu od k=1 do k=69 pozostaje jeszcze jedna nierozwiązana liczba - 42. Przypadek?

Zatem z zakresu od k=1 do k=77 pozostaje jeszcze jedna nierozwiązana liczba - 42. Przypadek?

Zatem z zakresu od k=1 do k=88 pozostaje jeszcze jedna nierozwiązana liczba - 42. Przypadek?

Zatem z zakresu od k=1 do k=99 pozostaje jeszcze jedna nierozwiązana liczba - 42. Przypadek?
A ile jest przypadków do k=1000? Same przypadki.

W zasadzie możecie to inaczej zrobić.
Róbcie kolejne liczby do sześcianu a wyniki <100 zapamiętujcie i zliczajcie. Rozkład liczbowy może być ciekawy.

8 minut temu, thikim napisał:

A ile jest przypadków do k=1000?

Jeżeli nawiązujesz do wypowiedzi @Jajcenty to myśle, że jednak "przypadek" odnosił się do samej liczby 42 ( https://pl.wikipedia.org/wiki/Wielkie_pytanie_o_życie,_wszechświat_i_całą_resztę ) a nie do samego zakresu.

Błędnie założyłeś że nie wziąłem tego pod uwagę.

To teraz wiedząc że ja wiedziałem o tym odniesieniu - przeczytaj jeszcze raz mój post

Bo dlaczego niby ma decydować do k=100? A może powinno być do k=666? (a tam raczej więcej jest takich liczb).
No ale gdyby się okazało że 42 jest jedyną liczbą do k-nieskończoności - to przyznaję - całkowicie się pomyliłem.

Ok to za glupi jestem. Bo nie widzę w tym wiekszej logiki

No właśnie ja też i o tym pisałem.
PS. I widzę dwuznaczność tej odpowiedzi i wieloznaczność poprzedniej - zanim ją mi tu ktoś odkrywczo wypomni.

O widzę edycję.

Juz tłumacze. Chodzi o kontekst.autor chciał policzyc wszystkie możliwe do stu i została 42. Koniec.

Edit

I z wszystkich możliwych dwucyfrowych została 42  przypadek ? 

Jakby liczył do 69 - też by została tylko 42

Ale chciał wyczerpać dwucyfrowe 

Mam pewien pomysł na optymalizację.

1. Za x podstawiamy 10¹⁴ i zaczynamy dodawać 1 w każdym kółku - może i tu da się coś z góry wyeliminować?
2. Za y zawsze podstawiamy liczbę ujemną z zakresu od -1 do -x/2 (drugą połowę sprawdzimy szukając z)
3. Szukamy liczby z, która da wynik możliwie najbliższy 42 lub -42 (tu jest jeszcze pole do popisu, jak to zrobić optymalnie). Jak nie uzyskamy równo 42 ani -42 to do x dodajemy 1 i zaczynamy od nowa.

Jak trafimy -42, to zmieniamy znaki i jest już wynik +42. Jeśli dobrze liczę daje to możliwość przeszukania absolutnie wszystkich możliwości... aż do limitu naszej cierpliwości lub pamięci komputera.

x zawsze będzie największą liczbą w zestawie i to jest ok, bo dodawanie i tak jest przemienne.

Jest szansa zmieścić się w typie long, który prawie sięga 10¹⁹. Ale sześciany tych liczb i tak się nie załapią, więc to chyba nic nie zmieni...

I tak stawiam, że po godzinie wciąż będziemy daleko od 10¹⁵...

A jesteś w stanie sprawdzić w jakim czasie jesteś stanie sprawdzić (na jednym rdzeniu i w ogóle bez fanaberii) "iterację" dla jednego ixa? Bo testowałem (co prawda teraz w pythonie ćwiczę sobie więc słabo o efektywność) i idzie to jakoś wolno. 

Tzn. teraz mam całkiem inne podejście. Nawet w sumie dwa równoległe pomysły. Jeden podobny do Twojego. Czyli wyznaczam X i dla niego szukam, ale to też nie wygląda aby miało iść super szybko (ale nie sprawdzałem tak dokładnie, bo skupiam się na tym drugim podejściu)

Godzinę temu, pogo napisał:

• Za x podstawiamy 10¹⁴ i zaczynamy dodawać 1 w każdym kółku - może i tu da się coś z góry wyeliminować?
• Za y zawsze podstawiamy liczbę ujemną z zakresu od -1 do -x/2 (drugą połowę sprawdzimy szukając z)
• Szukamy liczby z, która da wynik możliwie najbliższy 42 lub -42 (tu jest jeszcze pole do popisu, jak to zrobić optymalnie). Jak nie uzyskamy równo 42 ani -42 to do x dodajemy 1 i zaczynamy od nowa.

Na moje oko szukasz minimum F(x) = x^3 + (-x/2)^3 - 42 czyli zwykła optymalizacja. Wada jest taka, że x musi być sześcianem x = c^3, gdzie c - liczba całkowita.

2 godziny temu, Jajcenty napisał:

Na moje oko szukasz minimum F(x) = x^3 + (-x/2)^3 - 42 czyli zwykła optymalizacja. Wada jest taka, że x musi być sześcianem x = c^3, gdzie c - liczba całkowita.

 

Ale jak to? Jak to sprowadzileś do jednej niewiadomej? To mi sie wydaje strasznie łatwo obliczane. (Albo czegoś nie dostrzegam jak wrócę do domu to spróbuje 

59 minut temu, Afordancja napisał:

Ale jak to? Jak to sprowadzileś do jednej niewiadomej?

Nie ja. @pogo 

założył że rozwiązanie ma postać: x^3 + (-x/2)^3 + z^3 = 42. Jeśli dobrze zrouzmiałem....