RSS Feed
Precedenta
Următoarea

Problema 308

30 Octombrie 2010

Un program uimitor de generare de numere prime


Un program scris în limbajul de programare Fractran constă dintr-o listă de fracții.

Starea internă a mașinii virtuale Fractran e un număr întreg pozitiv care, la început, e inițializat cu o anumită valoare. Fiecare iterație a unui program Fractran înmulțește numărul care reprezintă starea cu prima fracție din listă, rezultatul fiind un număr întreg.

De exemplu, unul din programele Fractran scrise de John Horton Conway pentru a genera numere prime constă din următoarele 14 fracții:

17
91
,
78
85
,
19
51
,
23
38
,
29
33
,
77
29
,
95
23
,
77
19
,
1
17
,
11
13
,
13
11
,
15
2
,
1
7
,
55
1
.

Începând cu valoarea de inițializare 2, iterații succesive ale programului produc următorul șir:
15, 825, 725, 1925, 2275, 425, ..., 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

Puterile lui 2 care apar în acest șir sunt 22, 23, 25, ...
Se poate arăta că toate puterile lui 2 din acest șir au numere prime ca exponenți și că toate numerele prime apar ca exponenți ai puterilor lui 2, în ordinea corectă !

Dacă cineva folosește programul de mai sus pentru a rezolva problema nr. 7 de pe Project Euler (găsește al 10001lea număr prim), de câte iterații ar fi nevoie până când programul ar produce 210001-lea număr prim ?


>> Vezi problema originală <<