Oto dany ciąg:

0 1 1 2 3 5 8 3 1 4 5 9 4...

Każdy element tego ciągu jest liczbą całkowitą z przedziału <0;9>
Pierwszym elementem jest 0, drugim elementem jest 1.
Każdy następny element jest cyfrą jedności sumy dwóch poprzednich elementów.
Na przykładzie:

[1] => 0
[2] => 1
[3] => 1
[4] => 2
[5] => 3
[6] => 5
[7] => 8

.. na razie bez problemów ;)

[8] => 3 // gdyż 8+5 = 13
[9] => 1 // gdyż 3+8 = 11
...
etc



Program powinien pobierać jeden parametr - liczbę N
Pozostałe parametry będą ignorowane.
Program powinien wyświetlić na wyjściu pierwszą N-cyfrową liczbę pierwszą, która powstaje przy złączeniu N kolejnych elementów ciągu.


Np:
./a.out 1
N = 1
program wyświetli: 2



./a.out 2
N = 2
program wyświetli: 11



... etc :).

parametr N jest liczbą całkowitą dodatnią i nie będzie większa od miliona.
Czas - do niedzieli, 4 października 2009, godzina 00:17
W zadaniu ocenia się prędkość wykonania
Rozwiązania proszę nadsyłać na mejla :)
Let the game begin!

Mógłbyś podać jeszcze jakiś przykład?

Tak, prosimy o jeszcze jakiś przykład, może z większą liczbą N.

Ja może postaram się nakierować i przy okazji dowiem się czy dobrze zrozumiałem.

Mając taki ciąg, operujemy na nim
0 1 1 2 3 5 8 3 1 4 5 9 4 ... itd itd

mamy N = 1
poszukujemy więc liczby pierwszej o ilości cyfr = 1.
Liczbę taką tworzymy przy użyciu ciągu - kolejnych jego wyrazów (pogrubione)
0 1 1 2 3 5 8 3 1 4 5 9 4 ... itd itd (1 pogrubiona, bo tylko 1 cyfrę ma mieć)
najmniejszą liczbą pierwszą, jednocyfrową, utworzoną poprzez sklejenie wyrazów ciągu jest "2" - nie "1"!

Następnie mamy N = 2.
Więc będzie to liczba sklejona zawierająca dwie cyfry.
0 1 1 2 3 5 8 3 1 4 5 9 4 ... itd itd - sprawa wygląda analogicznie.

Ostatnim przykładem będzie N = 3
Liczba pierwsza, trzycyfrowa! Utworzona poprzez sklejenie kolejnych wyrazów!
Wklejam kilka pierwszych: 101, 103, 107, 109. W ciągu znajdziemy podciąg zawierający wyrazy "1,0,1", więc najmniejszą trzycyfrową liczbą pierwszą jest 101. (zaczyna się jakoś od 59 pozycji).

Mam nadzieje, że trochę pomogłem zrozumieć zadanie.

pierwsze tysiąc elementów ciągu:

011235831459437077415617853819099875279651673033695493257291011235831459437077415617853819099875279651673033695493257291011235831459
437077415617853819099875279651673033695493257291011235831459437077415617853819099875279651673033695493257291011235831459437077415617
853819099875279651673033695493257291011235831459437077415617853819099875279651673033695493257291011235831459437077415617853819099875
279651673033695493257291011235831459437077415617853819099875279651673033695493257291011235831459437077415617853819099875279651673033
695493257291011235831459437077415617853819099875279651673033695493257291011235831459437077415617853819099875279651673033695493257291
011235831459437077415617853819099875279651673033695493257291011235831459437077415617853819099875279651673033695493257291011235831459
437077415617853819099875279651673033695493257291011235831459437077415617853819099875279651673033695493257291011235831459437077415617
8538190998752796516730336954932572910112358314594370774156178538190998752796

jeżeli N = 3 to szukamy pierwszej trzycyfrowej liczby pierwszej w tym ciągu... patrząc na niego widzimy fragment

"291011"

i tu znajdujemy pierwszą trzycyfrową liczbę (101) i ona powinna zostać wyświetlona (101) :D

Kolega powyżej ma rację.
Jakieś pytania?

TBH napisał(a):parametr N jest liczbą całkowitą dodatnią i nie będzie większa od miliona.

Dobrze rozumiem? Milion cyfr?
Liczba gugol 10**100 to 101 cyfr, liczba jest tak duża, że nie występuje w naturze ( podobno liczba cząstek elementarnych we wszechświecie jest mniejsza).

TBH, poniosla wyobraznia ;]
dla n = 12 jeszcze fajnie sie liczy, potem to testowanie pierwszosci rozpieprza czasy ;]
a w przykladzie Candma dla N = 3 jest blad, pierwsza taka liczba to 617
-- o mam wynik dla n = 15 ;]
po 25 sekundach ;]

Masz rację Mak'u.
Źle zinterpretowałem treść.
Chodzi o pierwszą liczbę (pierwszą) 3 cyfrową, która składa się z wyrazów występujących jak najbliżej początku ciągu.

mak ma rację ;)

małe podsumowanie


mak.hs - błąd w kodzie, 1 nie jest liczbą pierwszą :)

Miałem w sumie nawet nie zaczynać rozwiązywać tego zadania, ale jakoś tak wyszło że je przczytałem i nasuneło mnie się tutaj pytanie takie troche absurdalne, bo skoro cały ciąg zaczyna się od cyfry 0, to czym ona jest i po kiego grzyba ona się tam znajduje? Czy jest ona tylko dlatego żeby zachować wizualny wygląd ciągu Fibonacci'ego, czy może jest tam po to żeby dać do zrozumienia, że jeżeli N=3 to wynikiem może być "liczba" 011, która składa się z 3 cyfr jakby nie patrzeć, ale z matematycznego punktu widzenia jest to liczba 11 (słownie jedenaście) (biorąc pod uwagę że kożystam z zapisu dziesiątkowego posługując się cyframi arabskimi)?
Więc powtórze pytanie: Po co jest ta cyfra 0 na początku tego ciągu?



I teraz już po rozwiązaniu tego zadania jeszcze jedno pytanie: Czy na 100% istnieją takie liczby pierwsze jakie trzeba znaleść w zadaniu? Jak tak to proszę o dowód matematyczny (hehehe)

doctor napisał(a):może jest tam po to żeby dać do zrozumienia, że jeżeli N=3 to wynikiem może być "liczba" 011, która składa się z 3 cyfr jakby nie patrzeć, ale z matematycznego punktu widzenia jest to liczba 11

Nie jestem aż taki zły :) 0 jest tam, żeby ładnie wyglądało - 011 nie jest liczone do zadania, tu nie ma nic podchwytliwego :D

doctor napisał(a):kożystam

RZ :)

doctor napisał(a):Czy na 100% istnieją takie liczby pierwsze jakie trzeba znaleść w zadaniu? Jak tak to proszę o dowód matematyczny (hehehe)

Dowód matematyczny?
cóż, liczb pierwszych jest nieskończenie wiele(twierdzenie Dirichleta, dowód Eulera), więc teoretycznie prawdopodobieństwo na natrafienie na dowolnie długą liczbę pierwsza w nieskończonym ciągu dąży do 1.

(nawet, jeżeli ciąg jest okresowy - jak powyższy)

No a weźmy na ten przykład N=25 i w tym momencie jest tzn. "dupa". Nie ma w tym ciągu takiej liczby ;) A program się zapętla, nie znajduje w danym okresie takiego ciągu, potem jest szukanie w następnym (łącząc te okresy), a jako że "okres jest większy niż 25", znaczy że takiej liczby nie ma w całym tym ciągu.

Ciekawe spostrzeżenie, PJWSTK robi dobry towar z Was :)

Więc nie dla każdego N da się obliczyć prawdziwy wynik - wiem to :D
... w takim razie mam już pomysł na następnie zadanie :>

Doktor zostaje odznaczony Orderem Ministra Internetu.

Czas wydłużony o 48h :)