Fractran : les algorithmes de Conway

http://mathworld.wolfram.com/FRACTRAN.html

 (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

 

cette liste très simple de 14 fractions, fabriquée par J H Conway et connue sous le nom de Primegame (un des « programmes » de FRACTRAN) permet d’engendrer tous les nombres premiers !!

Il y a 19 nombres différents dans ces 14 fractions.

On commence avec 2, on le multiplie successivement par chacune des fractions jusqu’à la première qui donne un produit qui soit entier, avec 2 cette fraction est 15/2 qui donne le produit :

2 x 15/2 = 15 

s’il n’existe aucune fraction qui donne un produit entier, le processus stoppe.

puis on recommence avec le produit, qui est ici 15, etc..

Ce calcul donne la suite :

http://oeis.org/A007542

dont on prouve que les puissances de 2 qu’elle contient sont :

2, 2^2, 2^3, etc.. et toutes les puissances de 2 avec un exposant premier, dans l’ordre !!!

la démonstration de ce fait, très simple, est donnée dans ce livre, en annexe :

http://books.google.fr/books?id=hekJ7JDMEVkC&pg=PA249&lpg=PA249&dq=fractran+primegame+conway&source=bl&ots=67N1SCDhW-&sig=wydfz5Tqr5jD2QB6YMCFmR2ot2M&hl=fr#v=onepage&q=fractran%20primegame%20conway&f=false

voir aussi

 http://fr.wikipedia.org/wiki/FRACTRAN

il existe une suite à neuf fractions, qui donne aussi les nombres premiers, à travers cette suite de résultats à partir de 10:

http://oeis.org/A183132/internal

(où ce sont les exposants de 10, et non plus de 2, qui sont les nombres premiers)

Il existe aussi un algorithme Pigame donnant toutes les décimales du nombre π = 3.14159…

http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/fractran

« 365  29  79 679 3159  83 473 638 434  89  17  79
  46 161 575 451  413 407 371 355 335 235 209 122

  31  41 517 111 305 23 73 61 37 19 89 41 833 53
183 115  89  83  79 73 71 67 61 59 57 53  47 43

86 13 23 67 71 83 475 59  41 1  1    1  1 89
41 38 37 31 29 19  17 13 291 7 11 1024 97  1

It computes pi(n), the nth digit of pi:  0 -> 3, 1 -> 1, 2 -> 4, …
i.e. when started on 2^n the next power of 2 to appear is 2^pi(n). »

 

Publicités

Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s