3x+1@home est un projet
de recherche distribué qui a pour
but de trouver des suites 3x+1 qui ont les "temps de vol" les plus longs
Le problème 3x+1 est également connu sous les
noms de conjecture de Syracuse, problème de
Collatz, Kabutani, Ulam, etc. Les
multiples noms de cette suite montrent la difficulté d'en
retrouver l’origine exacte. Cependant il semblerait que la
conjecture fût introduite par le mathématicien
allemand Lothar Collatz vers 1937. Par la suite, Helmut Hasse, un ami
de Lothar Collatz, de visite à l'université
américaine de Syracuse dans les années 1950
proposa le problème aux universitaires. Celui-ci remporta un
vif succès et la suite de Collatz, appelée aussi
algorithme de Hasse prît alors le nom de suite de Syracuse.
Entre temps, le mathématicien polonais Stanislas Ulam
répandît le problème dans
l'université de Los Alamos dans laquelle il travaillait
durant la seconde guerre mondiale. La suite devînt le
problème d'Ulam. Dix années plus tard (en 1960),
le problème fut repris par le mathématicien S.
Kakutani qui le diffusa dans les universités de Yale et
Chicago. Le problème prît alors le nom de
problème de Kakutani.
Cette conjecture mobilisa tant les mathématiciens durant les
années 1960, en pleine guerre froide, qu'une plaisanterie
courut selon laquelle ce problème était l'oeuvre
d'un
complot soviétique pour ralentir la recherche
américaine. Plus sérieusement, Paul
Erdős disait
à propos de la conjecture de Collatz : « les
mathématiques ne sont pas encore prêtes pour de
tels problèmes ». Il proposa d'offrir 500 $
à quiconque lui donnerait une solution.
Vous trouverez l'exposé détaillé de
cette conjecture sur ce site : au format
pdf,
flash
ou word
Ou dans cette
article de Jean-Paul DELAHAYE publié en 1998 dans
le magazine Pour la Science
La conjecture
de Syracuse
:
Le mécanisme est extrêmement simple
Prenez tout nombre entier N plus grand que zéro
(un entier naturel)
S'il est pair, on le divise par 2. S'il est impair, on le
multiplie par 3 et on ajoute 1
Répétez l'opération
jusqu'à obtenir le nombre 1
La conjecture tient dans
l'hypothèse mathématique
selon laquelle les suites de Syracuse de tous les nombres
positifs tombent au final sur le nombre un.
Quelques exemples :
5 -> 16 -> 8 -> 4 -> 2 -> 1
Le nombre 1 a été atteint en 5
étapes. Le temps de vol est donc de 5
18 -> 9 -> 28 -> 14 -> 7 -> 22
-> 11 -> 34 ->
17 -> 52 -> 26 -> 13 -> 40 -> 20
-> 10 -> 5 ->
16 -> 8 -> 4 -> 2 -> 1
Le nombre 1 a été atteint en 20
étapes. Le temps de vol est donc de 20
Vous trouverez plus d'informations sur la conjecture de Syracuse sur Wikipédia
Que signifie le temps de
vol d'une suite de Syracuse ?
Le temps de vol correspond au nombre d'étapes
nécessaires pour atteindre le nombre 1.
Que recherche le projet
3x+1@home ?
3x+1@home recherche les vols de durée record. Comme vous
pouvez
vous y attendre, les vols des grands nombres entiers durent longtemps,
ainsi le
projet recherche des grands n = durée de vol / Log2(N).
Si il s'avère qu'un N a un temps de vol infini,
l'application le fera
remarquer.
Un large éventail de nombres entiers ont
déjà été passés
au crible par différents projets, il n'y a donc pas besoin
de les vérifier une nouvelle fois.
Ce projet de recherche s'intéressera donc aux nombres
entiers compris entre 271 et 272,
une gamme de nombre qui n'a pas encore été
testé.
3x+1@home examinera t'il
d'autres caractéristiques du
problème de Syracuse (facteur d'expansion, temps de vol en
altitude, etc) ?
Non, l'application est optimisée pour calculer la
durée de vol le plus rapidement possible
Les résultats :
Le 6 août 2008, [AF>EDLS] Pitheque (L'Alliance
Francophone) découvrait avec le nombre 2.361.235.441.021.745.907.775
une suite de Syracuse avec un temps de vol records en 2284
étapes.
Highest stopping times found (sieve application)
: Plus grandes
durée de vol découverte (application sieve) Durée de vol : 2284 : 3 suites ont
été découvertes (voir)
Durée de vol : 2240 : 1 suite a été
découverte (voir)
Durée de vol : 2222 : 2 suites ont
découvertes (voir)
....
L'image ci-dessous représente les durées de vol
des nombres entiers compris entre 271 et 272,
En noir, sont représentés tous les
vols de nombres
entiers
inférieurs à 1500 étapes
En bleu, sont représentés tous les vols
de nombres
entiers compris entre 1500 et 1600
étapes
En vert, tous les vols compris entre 1600 et 1700 étapes
....
En rouge, tous les vols de nombres
entiers se déroulant durant plus de 2000
étapes
En gris tous les nombres entiers en cours de calcul
En dessous de chaque couleur, vous pouvez voir entre
parenthèse le nombre de vols testés et
appartenant
à chacune des catégories.
Cet article a été publié le 08-03-2008 22:01. Vous pouvez suivre les commentaires suscités par cet article grâce au fil RSS 2.0. Vous pouvez laisser un commentaire.
Dernière mise à jour 10-08-2008 15:38
Vos commentaires (0)
Seul les utilisateurs enregistrés peuvent commenter un article.
