Membres à l'honneur: [AF>2TF]Rick () | [AF>Libristes] Kether () | Dao Heng Liu () | kdrt () | [AF>FRANCE>EST>ALPES] maxxub () | [AF>libristes] overclockman () | [AF>Quebec]MDodier () | JEROMINATOR (200 000) | JPBonnefoy (20 000) | Tagadaben (40 000) | popy (4 000 000) |

Collatz Conjecture

3x+1

Le projet initial s'appelait 3x+1@home. La structure et les résultats de ce projet ont été repris par le projet Collatz Conjecture. Plusieurs innovations ont été apportées notamment des applications optimisées SSE et SSE2 ainsi que la possibilité de faire calculer les cartes graphiques Nvidia et ATI.

Les résultats du projet 3x+1@home peuvent être téléchargés ici (fichier de 77,0 Mo). Vous y trouverez tous les nombres découverts ayant une durée de vol > 1000 (un nombre par ligne).

 

Collatz Conjecture

Recherche de suites de Syracuse aux durées de vol record


INSCRIPTION  

OS / Clients : Windows MacOS Linux Nvidia ATI Clients 64bits

Télécharger Boinc (tutoriel)

URL du projet : http://boinc.thesonntags.com/collatz/

Applications Optimisés : ICI

Délai retour, RAM (il faut choisir votre application) : ICI


Liens du Projet
L'Alliance Francophone
Statistiques
  • Début du projet 3x+1@home: 18 février 2008
  • Début du projet Collatz Conjecture : 11 Juin 2009
  • Statut : Alpha test

Les applications Nvidia sont envoyées automatiquement à partir du moment ou votre ordinateur est équipé d'une carte graphique compatible avec la technologie CUDA et que vous avez répondu "yes" à la question "Use Graphics Processing Unit (GPU) if available" dans les préférences Collatz Conjecture de votre compte.



Collatz Conjecture 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'œuvre 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

  1. Prenez tout nombre entier N plus grand que zéro (un entier naturel)
  2. S'il est pair, on le divise par 2. S'il est impair, on le multiplie par 3 et on ajoute 1
  3. 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 nombres qui n'a pas encore été testée.

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