Jump to content
Forum Kopalni Wiedzy

Recommended Posts

Profesor matematyki Andrew Booker z University of Bristol rozwiązał zagadkę matematyczną sprzed 64 lat. Zagadka brzmi: jak wyrazić liczbę 33 za pomocą sumy trzech liczb podniesionych do potęgi trzeciej. Równanie wygląda w następujący sposób: x3+y3+z3=33 i jest przykładem równania diofantycznego. Nazwano je tak od imienia greckiego matematyka Diofantosa z Aleksandrii, który przed 1800 lat zaproponował podobne równania.

Na przykład jeśli k=8, to równanie wygląda następująco 23+13+(-1)3=8.

Matematycy, którzy mierzą się z równaniami diofantycznymi, wiedzą na przykład, że liczby, z których po podzieleniu przez 9 pozostaje reszta 4 lub 5, nie mogą być rozwiązane za pomocą równań diofantycznych. To wyklucza 22 liczby z przedziału od 1 do 100. Jednak 78 pozostałych liczb powinno mieć rozwiązania. Dotychczas nie udało się znaleźć rozwiązania dla 33 i 42.

Booker chciał znaleźć nowe rozwiązania dla wszystkich liczb mniejszych niż 100, dla których rozwiązania można znaleźć. Stworzył więc algorytm komputerowy, którego zadaniem było rozwiązanie równania x3+y3+z3=k, a który mógł za „x”, „y” oraz „z” podstawiać liczby o wartości do 1016. Uczony przyznaje, że nie spodziewał się, że znajdzie też pierwsze w historii rozwiązanie dla k=33. Równanie wygląda następująco: (8.866.128.975.287.528)3 + (–8.778.405.442.862.239)3 + (–2.736.111.468.807.040)3 = 33

Zatem z zakresu od k=1 po k=100 pozostała jeszcze jedna nierozwiązana liczba – 42. Dzięki pracy Bookera wiadomo, że do jej rozwiązania trzeba użyć liczb większych niż 1016.


« powrót do artykułu

Share this post


Link to post
Share on other sites
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*1048 punktów. Nie wróżę sukcesów brute force'om

Share this post


Link to post
Share on other sites
Posted (edited)
1 godzinę temu, Jajcenty napisał:

Przypadek? Nie sądzę.

:D

 

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ć

Edited by Afordancja

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Posted (edited)
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

Edited by Afordancja

Share this post


Link to post
Share on other sites
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 [-1016 ; 1016] 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 n3 można te minima dość szybko znajdować.

Share this post


Link to post
Share on other sites
Godzinę temu, Jajcenty napisał:

Korzystając z ciągłości n3 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 [-1016 ; 1016] 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 :)

Share this post


Link to post
Share on other sites

[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ć :)

Share this post


Link to post
Share on other sites

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

Challenge accepted :P

 

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

Share this post


Link to post
Share on other sites
Posted (edited)

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

Edited by Ergo Sum

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Posted (edited)
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? :D 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.

Edited by thikim

Share this post


Link to post
Share on other sites
Posted (edited)

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.

Edited by thikim

Share this post


Link to post
Share on other sites
Posted (edited)

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.

Edited by thikim

Share this post


Link to post
Share on other sites
Posted (edited)

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 ? 

Edited by Afordancja

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Posted (edited)

Mam pewien pomysł na optymalizację.

  1. Za x podstawiamy 1014 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 1019. 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 1015...

Edited by pogo

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites
Posted (edited)
Godzinę temu, pogo napisał:
  • Za x podstawiamy 1014 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.

 

Edited by Jajcenty

Share this post


Link to post
Share on other sites
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 

Share this post


Link to post
Share on other sites
59 minut temu, Afordancja napisał:

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

Nie ja. @pogo :D

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Similar Content

    • By KopalniaWiedzy.pl
      Brakthrough Prize Foundation ustanowiła nagrodę na cześć Marjam Mirzachani, jedynej kobiety, która zdobyła Medal Fieldsa. Maryam Mirzakhani New Frontiers Prize o wartości 50 000 USD będzie przyznawana matematyczkom, które w ciągu dwóch lat przed otrzymaniem nagrody zrobiły doktorat i mogą pochwalić się wyjątkowymi osiągnięciami.
      Marjam Mirzachani urodziła się w 1977 roku w Teheranie. Jej talent matematycznym ujawnił się w szkole średniej. W 1994 roku zdobyła złoty medal na międzynarodowej olimpiadzie matematycznej. Pięć lat później ukończyła matematykę na Uniwersytecie Technologicznym Szarif, w roku 2004 uzyskała doktorat na Uniwersytecie Harvarda, a w 2009 roku została profesorem matematyki na Uniwersytecie Stanforda.
      W 2014 roku, jako pierwsza i jedyna dotychczas kobieta otrzymała Medal Fieldsa. Ten „matematyczny Nobel” przyznawany jest raz na cztery lata wyróżniającym się matematykom, którzy nie ukończyli 40. roku życia. Od 1936 roku wyróżniono nim zaledwie 60 osób. Mirzachani otrzymała go za badania dynamiki i geometrii powierzchni Riemanna i przestrzeni moduli na tych powierzchniach. O jej wyjątkowym osiągnięciu pisaliśmy szczegółowo przed pięcioma laty.
      W 2013 u Mirzachani wykryto raka piersi. Matematyczka zmarła w 2017 roku.

      « powrót do artykułu
    • By KopalniaWiedzy.pl
      Gdy przed 5 miesiącami profesor Andrew Booker z University of Bristol nieco przy okazji rozwiązał równanie diofantyczne x3+y3+z3=33, postanowił pójść za ciosem i znaleźć rozwiązanie dla ostatniej nierozwiązanej liczby z zakresu 1–100. Równania diofantyczne zostały nazwane od Diofantosa z Aleksandrii, który przed 1800 laty zaproponował podobne równanie.
      W 1954 roku naukowcy z University of Cambridge rozpoczęli poszukiwania rozwiązania dla równań x3+y3+z3=k, dla k z zakresu od 1 do 100.
      Matematycy, którzy próbują je rozwiązać wiedzą, że liczby, z których po podzieleniu przez 9 zostaje reszta 4 lub 5 nie mogą być rozwiązane z pomocą równań diofantycznych. To oznacza, że z zakresu 1–100 nie można rozwiązać 22 liczb, ale dla 78 powinno istnieć rozwiązanie. Jeszcze do niedawna nie znano rozwiązania dla liczb 33 i 42. W kwietniu profesor Booker znalazł rozwiązanie dla 33 oraz stwierdził, że rozwiązania dla 42 należy szukać wśród liczb większych niż 1016.
      Uczony postanowił pójść za ciosem i poprosił o pomoc profesora matematyki Andrew Sutherlanda z MIT, który specjalizuje się w masywnych obliczeniach równoległych. Obaj uczeni wykorzystali urządzenie, które przypomina usługi planetarnego przetwarzania danych „Deep Thought” opisane w „Autostopem przez galaktykę”, którzy dał odpowiedź na wielkie pytanie o życie, wszechświat i całą resztę. Do znalezienia odpowiedzi na równanie x3+y3+z3=42 wykorzystano bowiem Charity Engine, czyli sieć ponad 500 000 domowych pecetów, których użytkownicy udostępniają ich moc obliczeniową w czasie, gdy maszyny nie są używane. Rozwiązanie, które wymagało ponad miliona godzin obliczeń wygląda następująco (-80538738812075974)3+(80435758145817515)3+(12602123297335631)3=42. Tym samym znamy już wszystkie możliwe rozwiązania równań diofantycznych dla liczb z zakresu 1–100.
      Profesor Booker stwierdził, że czuje ulgę. W tej grze nie można być pewnym, że znajdzie się odpowiedź. [...] Mogliśmy znaleźć odpowiedź po kilku miesiącach, ale mogło się też okazać, że przez kolejne 100 lat nikt jej nie znajdzie.

      « powrót do artykułu
    • By KopalniaWiedzy.pl
      Przy wyższych temperaturach kobiety lepiej wypadają w zadaniach matematycznych i słownych. U mężczyzn jest dokładnie na odwrót (w ich przypadku zależność między temperaturą a osiągami jest jednak słabiej zaznaczona).
      Badanie sugeruje, że płeć jest ważnym czynnikiem nie tylko przy określaniu wpływu temperatury na komfort, ale i na produktywność czy osiągi poznawcze.
      Jest udokumentowane, że kobiety wolą w pomieszczeniach wyższe temperatury niż mężczyźni. Dotąd sądzono jednak, że to wyłącznie kwestia osobistych preferencji. Nasz zespół ustalił, że nie chodzi tylko o to, czy czujesz się dobrze, czy nie i że temperatura wpływa na osiągi w kluczowych dziedzinach: w matematyce, zadaniach słownych i we wkładanym wysiłku - opowiada prof. Tom Chang z Uniwersytetu Południowej Kalifornii.
      W eksperymencie wzięło udział 543 studentów z WZB Berlin Social Science Center. W ciągu sesji ustawiano różne zakresy temperaturowe (od ok. 16 do 33 stopni Celsjusza). Ochotnicy mieli wykonywać 3 typy zadań (zachętą do pracy była nagroda pieniężna): 1) matematyczne, polegające na dodaniu bez kalkulatora pięciu dwucyfrowych liczb, 2) słowne, przy którym z zestawu 10 liter należało utworzyć w zadanym czasie jak najwięcej słów i 3) test świadomego myślenia (ang. Cognitive Reflection Test, CRT).
      Naukowcy wykryli znaczącą zależność między temperaturą otoczenia i wynikami osiąganymi w zadaniach matematycznym i słownym. Ani u kobiet, ani u mężczyzn temperatura nie miała wpływu na wyniki testu CRT.
      Jedną z najbardziej zaskakujących rzeczy jest to, że nie uciekaliśmy się wcale do skrajnych temperatur. Nie chodzi o trzaskający mróz czy upał. Znaczące zróżnicowanie osiągów widać nawet przy temperaturach rzędu 60-75 stopni Fahrenheita [15,5-24 stopni Celsjusza], co jest w końcu stosunkowo normalnym zakresem wartości.
      Autorzy artykułu z pisma PLoS ONE podkreślają, że poprawa osiągów poznawczych kobiet w wyższych temperaturach wydaje się napędzana głównie wzrostem liczby podawanych odpowiedzi. Po części można to interpretować jako skutek wzrostu wkładanego wysiłku.
      U mężczyzn spadek osiągów poznawczych przejawiał się mniejszą liczbą zgłaszanych odpowiedzi.
      Wzrost osiągów kobiet jest większy (daje się też precyzyjniej oszacować) niż spadek osiągów u mężczyzn.
      Amerykańsko-niemiecki zespół podkreśla, że uzyskane wyniki rzucają nieco światła na nieustającą walkę o ustawienia termostatu w biurach. Wg naukowców, by zwiększyć produktywność w mieszanych płciowo zespołach, ustawienia temperatury powinny być wyższe niż przy obecnych standardach.

      « powrót do artykułu
    • By KopalniaWiedzy.pl
      Zapach kawy poprawia wyniki osiągane w matematyce.
      Naukowcy z Instytutu Technologicznego Stevensa odkryli, że woń kawy pomaga ludziom osiągać lepsze wyniki w analitycznej części testu GMAT (Graduate Management Aptitude Test).
      Nie chodzi tylko o to, że kawowy zapach pomagał ludziom lepiej wypadać w zadaniach analitycznych, co samo w sobie byłoby już interesujące. [Istotne jest to, że czując kawę] badani uważali, że lepiej im pójdzie, a my wykazaliśmy, że to oczekiwanie przynajmniej częściowo odpowiadało za wyższe wyniki - opowiada prof. Adriana Madzharov.
      Oznacza to więc, że mimo nieobecności kofeiny, wyczuwanie zapachu kawy miało skutek podobny do wypicia naparu, co sugeruje efekt placebo woni kawy.
      W ramach eksperymentu ok. 100 studentów zarządzania rozwiązywało test z algebry składający się z 10 zadań. Ochotników podzielono na 2 grupy: jedna pracowała w pomieszczeniu, w którym czuć było zapach kawy, a druga w kontrolnym pokoju bez woni. Okazało się, że pierwsza grupa uzyskiwała znacząco lepsze wyniki.
      Chcąc sprawdzić, czy poprawę myślenia można po części wyjaśnić oczekiwaniami, że zapach kawy zwiększy czujność i w ten sposób polepszy wyniki, spytano kolejne osoby (ponad 200) o przekonania związane z różnymi woniami. Ludzie uważali, że w porównaniu do zapachu kwiatowego lub braku woni, w obecności zapachu kawy będą bardziej czujni i naenergetyzowani. Spodziewali się, że ekspozycja na zapach kawy poprawi też ich osiągnięcia w zadaniach umysłowych. Wyniki sugerują zatem, że oczekiwania co do uzyskiwanych wyników można wyjaśnić przekonaniem, że sama woń kawy sprawia, że ludzie są bardziej czujni/sprawni umysłowo.
      W przyszłości Madzharov chce sprawdzić, czy kawowe zapachy wywierają podobny efekt placebo w przypadku innych typów zadań, np. rozumowania werbalnego. Wg niej, spostrzeżenie, że woń kawy działa na rozumowanie analityczne jak placebo, znajdzie sporo zastosowań praktycznych, w tym biznesowych.

      « powrót do artykułu
×
×
  • Create New...