Pewien wykopowicz jako hasło do wykopu ustawił sobie liczbę ośmiocyfrową postaci XY (cyfry liczb X i Y zapisane kolejno), gdzie X i Y to dwie liczby czterocyfrowe. Wykopowicz ten wie, że jeśli zapomni hasła, to może je odtworzyć w następujący sposób:
- X jest większe od Y,
- X i Y są względnie pierwsze,
- liczba ośmiocyfrowa XY jest wyrazem ciągu, którego pierwszym wyrazem jest X, drugim wyrazem jest Y, a każdy kolejny wyraz to suma dwóch wyrazów poprzedzających.
@argothiel: Spóźniłbyś się 22, gdybym sobie nie ubzdurał, że jak X i Y są czterocyfrowe, to XY=1000X+Y a nie XY=10000X+Y... i zastanawiaj się tu człowieku, dlaczego rozwiązanie nie istnieje :P
@argothiel: Liczenie po kolei (F(n+1)-1)/(10000-F(n)), gdzie F(n) to n-ty wyraz ciągu Fibonacciego. Wynik miał oczywiście być liczbą między 1 a 10 przedstawioną jako nieskracalny ułamek liczb czterocyfrowych, tzn. o czterocyfrowym liczniku i mianowniku.
@argothiel: informacja, że liczby są tutaj względnie pierwsze była dosyć kluczowa i mi też udało się znaleźć rozwiązanie dopiero jak zrozumiałem co ta informacja daje ;)
@argothiel: Ja też próbowałem bruteforce, ale w złym miejscu postawiłem instrukcję warunkową i nie mogłem dojść, czemu wynik nie istnieje. Paradoksalnie informacja o względności liczb - w przypadku bruteforce - jedynie spowolniła mi program. Może dlatego, że zastosowałem tylko algorytm Euklidesa na sprawdzanie, czy NWD równa się 1.
Pewien wykopowicz jako hasło do wykopu ustawił sobie liczbę ośmiocyfrową postaci XY (cyfry liczb X i Y zapisane kolejno), gdzie X i Y to dwie liczby czterocyfrowe. Wykopowicz ten wie, że jeśli zapomni hasła, to może je odtworzyć w następujący sposób:
- X jest większe od Y,
- X i Y są względnie pierwsze,
- liczba ośmiocyfrowa XY jest wyrazem ciągu, którego pierwszym wyrazem jest X, drugim wyrazem jest Y, a każdy kolejny wyraz to suma dwóch wyrazów poprzedzających.
Podaj hasło tego wykopowicza.
Komentarz usunięty przez autora
Edit: O rajuśku, nie można podać swojego hasła w komentarzach, bo wykop dla bezpieczeństwa gwiazdkuje!
Rzeczywiście!
@argothiel: informacja, że liczby są tutaj względnie pierwsze była dosyć kluczowa i mi też udało się znaleźć rozwiązanie dopiero jak zrozumiałem co ta informacja daje ;)
Kolejna zagadka będzie do 5 minut.
for (x=1000; x<=9999; x++)
for (y=1000; y
if (x*4181 + y*6765 == 10000*x + y)
printf ("%d %d\n", x, y);
Tak czy owak, rozwiązanie w Pythonie: http://ideone.com/mxN53