Collatz et les puissances de 2

[syrac]

Bah, le discours habituel des pauvres génies incompris que la caste des mathématiciens englués dans leurs certitudes refuse de reconnaître à leur juste valeur

Pas exactement. C'est le côté psycho-rigide de certains, enfermés dans leur tour d'ivoire au point de se sentir supérieur au commun des mortels, qui représente le véritable problème. Ils font du darwinisme à leur manière : dans l'échelle de l'évolution on trouve les minéraux, les plantes, les animaux, les hommes, et les mathématiciens.

[syrac]

Moi je trouve ta démarche plutôt sympa. Elle m'a permis de me mettre à réfléchir (enfin) à ce problème de manière un peu poussée par l'intermédiaire de l'étude de tes algorithmes et de ton approche.

Merci, une pensée qui dans le contexte actuel vaut son pesant d'or !

Il est simplement dommage que tu n'essaies pas de comprendre l'aspect mathématique des réponses qui te sont faites pour essayer, toi aussi, de progresser dans l'étude de ce problème.

Il est clair que les nombreuses questions que j'ai posées ici à propos de tel ou tel aspect de mon travail de recherche (comme le fait de savoir pourquoi l'expression du dernier terme d'une suite impaire est toujours égale à 1), dénotent un certain besoin d'obtenir des réponses plus solidement construites que le résultat de quelques transformations algébriques ou celui d'expérimentations sous Mathematica. D'un autre côté, beaucoup de fondateurs des mathématiques modernes appartenaient à cette autre caste aujourd'hui baptisée "amateurs", par opposition à la précédente, comme Fermat et tant d'autres, ce que je trouve quelque part rassurant et me permet de préserver ma foi en l'homme. Preuve que "ne pas savoir" n'est pas toujours un obstacle insurmontable.

[syrac]

En me relisant je m'aperçois que mes propos pourraient ne pas être interprétés dans le sens que je leur ai donné. Quand j'utilise les termes "fondateurs des mathématiques modernes" et que j'évoque Fermat, je veux seulement dire que beaucoup de ceux qui ont largement contribué au progrès des mathématiques, et des sciences en général, étaient des amateurs, ce qui semble du reste logique puisqu'à ces époques il y avait seulement des gens versés dans certaines pratiques ou savoirs, mais qui n'avaient pas le statut tel qu'on le conçoit aujourd'hui de professionnels. Tout ceci pour dire qu'à la place d'amateurs j'aurais dû utiliser le terme de passionnés, d'enthousiastes. Et c'est dans la passion qu'on devient véritablement créatif, ce qui est le cas de beaucoup d'amateurs qui se livrent à leur activité favorite sans rien en attendre qu'un peu d'adrénaline.

Bref, en aucun cas je ne tentais de comparer ce que je fais à ce qu'ils ont fait, j'espère que chacun l'aura compris.

[syrac]

Voici comment expliquer le fait que l'exposant des puissances de 2 est toujours soit pair soit impair. Mais d'abord un petit rappel : dans l'image ci-dessus, predN(n) calcule les prédécesseurs possibles de n, un terme d'une suite impaire. Si p est l'un d'eux, alors n = (3p+1)/2^(le nombre sous lui). Appelons p0, p1, p2, ... une suite de prédécesseurs, p0 représentant le plus petit.

p0
p1 = 4p0+1 = 2^2*p0+(2^2-1)/3
p2 = 4p1+1 = 4(4p0+1)+1 = 16p0+5 = 2^4*p0+(2^4-1)/3
p3 = 4p2+1 = 4(16p0+5)+1 = 64p0+21 = 2^6*p0+(2^6-1)/3
p4 = 4p3+1 = 256p0+85 = 2^8p0+(2^8-1)/3
etc.

Après simplification on obtient



Pour faire ces calculs facilement :

suitePred[p_, min_, max_] := Table[(2^x (3p+1)-1)/3, {x, min, max, 2}]

Dans ce qui suit on calcule les 9 premiers prédécesseurs de 5 en connaissant le premier, 3 :

suitePred[3,0,16] = 3, 13, 53, 213, 853, 3413, 13653, 54613, 218453

On aurait obtenu le même résultat avec suitePred[213,-6,10], et de nombreuses autres manières.

Ou comment remplacer un processus qui requérait 250 000 itérations par un autre qui en requiert 9.

[Sylviel]

C'est la raison pour laquelle je m'adresse à des mathématiciens confirmés, avec l'espoir qu'ils fassent autre chose que de me prendre de haut parce que je n'appartiens pas à leur caste.

Le problème n'est pas une question de "caste" mais de principes de discussion.

Tu fais des affirmations du type : "je l'ai montré sur un grand nombre de cas donc ça doit être vrai pour tous les cas, ça ne sers à rien de chercher à le démontrer", et en même temps tu prétends vouloir apporter des choses aux mathématiciens. C'est incohérent.

Il faut que tu acceptes que le problème est mathématique, et que la réponse à la question "est-ce qu'une suite telle que ... converge toujours vers 1" sera une démonstration (éventuellement aidée d'un ordinateur). Si tu veux apporter ta pierre à la question il y a plusieurs manières de le faire :
- faire des observations, basées sur des tests numériques qui pourront aider à comprendre et à batir une preuve. Ce ne sera jamais une preuve, mais cela peut donner des indices sur comment l'obtenir.
- démontrer des propriétés sur la suite en espérant qu'elles permettent un jour d'arriver à une démonstration complète.

Que tu soit amateur, étudiant ou professionnel ne change rien à tes contributions. La question est simplement : peux-tu donner une preuve valable d'une proposition ?
as-tu observé un comportement remarquable sur un grand nombre de cas qui vaudrait la peine d'être démontrée ?

[syrac]

Le problème n'est pas une question de "caste" mais de principes de discussion.

Je croyais qu'il était clair que mes propos visaient une cible précise. C'est dans l'idée de cette personne que germe probablement l'idée de caste, pas dans la mienne.

Tu fais des affirmations du type : "je l'ai montré sur un grand nombre de cas donc ça doit être vrai pour tous les cas, ça ne sers à rien de chercher à le démontrer"

C'est sûr que ce n'est pas le meilleur moyen d'intéresser des gens rompus aux démonstrations. Disons que c'est une hypothèse qui me permet d'avancer au lieu de passer mon temps à faire des démonstrations, ce qu'il sera de toute façon toujours possible de faire ultérieurement. Je te cite :

- faire des observations, basées sur des tests numériques qui pourront aider à comprendre et à batir une preuve. Ce ne sera jamais une preuve, mais cela peut donner des indices sur comment l'obtenir.
- démontrer des propriétés sur la suite en espérant qu'elles permettent un jour d'arriver à une démonstration complète.

Il semble que tu comprennes mieux ma démarche que tu ne veux l'avouer ! :lol3:

et en même temps tu prétends vouloir apporter des choses aux mathématiciens. C'est incohérent.

Entendons-nous bien, je ne cherche pas à apporter quoi que ce soit aux mathématiciens, sauf peut-être lorsque je dis que que la notion de cycle trivial est une erreur dans laquelle nombreux sont tombés, et pas uniquement des mathématiciens. Sais-tu que lorsque tu dis ça à quelqu'un qui a consacré du temps à l'étude de ce problème, qui ou quoi qu'il puisse être, il te regarde avec des yeux ronds et considère que tu ne parles pas des suites de Collatz ? J'en ai fait plusieurs fois l'expérience. Les notions de durée de vol et de cycle trivial sont tellement ancrées dans les esprits qu'elles ont finies par devenir le paradigme. Si tu les évinces tu deviens un extraterrestre et plus personne ne t'écoute. S'il fallait absolument trouver ce que j'apporte, il faudrait sans doute regarder dans cette direction : jamais, à aucun moment, je ne parle de durée de vol et de cycle trivial.

Il faut que tu acceptes que le problème est mathématique, et que la réponse à la question "est-ce qu'une suite telle que ... converge toujours vers 1" sera une démonstration (éventuellement aidée d'un ordinateur).

Bien sûr ! Je ne prétends aucunement que c'est via la technique du macramé qu'on parviendra à une solution ! C'est un problème mathématique qui ne peut se résoudre que par les mathématiques. La seule question qui mérite d'être posée est de savoir si ce problème est à la hauteur de sa réputation de complexité, ce que l'avenir nous dira sans doute. Ou peut-être que c'est tout simplement moi qui ne suis pas à la hauteur, va savoir !

as-tu observé un comportement remarquable sur un grand nombre de cas qui vaudrait la peine d'être démontrée ?

Oui, absolument.

[syrac]

Voici une manière directe de calculer le plus petit prédécesseur d'un terme d'une suite impaire :

as-tu observé un comportement remarquable sur un grand nombre de cas qui vaudrait la peine d'être démontrée ?

En voici un exemple.

[syrac]

Voici une variante de la fonction suitePred() ci-dessus. Les valeurs du paramètre d peuvent être 0 (par défaut), 1 ou 2 :

0 : renvoie la suite de prédécesseurs.
1 : renvoie la suite des prédécesseurs non divisibles par 3.
2 : renvoie la suite des prédécesseurs divisibles par 3.



Pour construire une suite impaire par la fin on pourrait à chaque étape générer une suite de prédécesseurs non divisibles par 3 puis en sélectionner un au hasard. J'ai essayé, mais aussi incompréhensible que ça paraisse la suite croît très rapidement vers n0, de manière bien plus radicale qu'avec la fonction suiteAleatoire(). Il est possible que ça vienne de la manière dont on effectue ce choix aléatoire, ou plus exactement de la fonction utilisée.

[Robot]

Ceci montre qu'il existe une relation directe entre n et son plus petit prédecesseur, et qu'on n'a pas besoin de passer par les tests.

C'est ce que j'ai écrit depuis le début.

Il reste bien entendu à éliminer tout prédecesseur potentiel qui serait divisible par 3, là encore sans passer par des tests, mais c'est une autre histoire.

Ca ne reste pas, c'est déjà fait. Je réécris ce que j'ai déjà écrit, sous une forme plus proche de tes notations. Les désignent les exposants tels que soit de la forme avec impair non divisible par .
Si , les qui conviennent sont les et les , le plus petit est 2
Si , les qui conviennent sont les et les , le plus petit est 1
Si , les qui conviennent sont les et les , le plus petit est 2
Si , les qui conviennent sont les et les , le plus petit est 3
Si , les qui conviennent sont les et les , le plus petit est
Si , les qui conviennent sont les et les , le plus petit est 1
Ceci résulte de considérations modulaires élémentaires.

[syrac]

Comment appelles-tu le fait d'avoir à calculer n mod 18 puis de prendre une décision en fonction du résultat ?

[Robot]

Sachant que est impair, c'est en fait modulo 9 qui décide : les six cas ci-dessus correspondent à .
Calculer modulo 9 (ou même modulo 18), j'appelle ça peanuts : tu penses vraiment que calculer le reste de la division par 9 a un coût prohibitif ? Tu vois une différence avec ton modulo 6 ? :ptdr:
J'ajoute une chose : la distinction des cas suivant la classe modulo 9 n'est pas une "complication" qu'on peut éviter : d'une part ça n'a vraiment rien de compliqué (rien du tout pour un système de calcul formel comme Mathematica ou autre), d'autre part les exposants possibles sont effectivement différents suivant la classe modulo 9. C'est la vie !

[syrac]

Non, en termes de coût le calcul du modulo 9 n'est bien sûr pas prohibitif. Mais tout bien réfléchi, où est le vrai problème ? Il réside dans la volonté de construire une suite impaire en partant de la fin et qui comptera un nombre arbitrairement choisi de termes, en l'occurrence N, ce qui entraîne l'obligation de trouver des prédécesseurs qui ne soient pas divisibles par 3, sauf le dernier, n0. Pour évacuer ce problème il suffit de tourner la phrase autrement ; au lieu de parler du "calcul d'une suite impaire de N termes" on parlera du "calcul d'une suite impaire comportant un maximum de N termes" ! Sinon tout ça pourrait s'emballer et produire une suite tellement longue qu'elle en deviendrait inexploitable et ne voudrait strictement plus rien dire.

Pour commencer je vais poser M = n (9 - n mod 6) et remplacer p0 = (M - 2)/6 par (M/2 - 1)/3, afin d'uniformiser les expressions de p0, p1, p2, etc. Ensuite on fait p1 = 4 p0+1 = 4 ((M/2 - 1)/3)+1 = (2M - 1)/3, puis p2 = 4 p1+1 = (8M - 1)/3, etc. Au final on obtient pour la suite p0, p1, p2, ... les expressions

(M/2 - 1)/3, (2M - 1)/3, (8M - 1)/3, (32M - 1)/3, etc., c'est-à-dire (M 2^u - 1)/3, où u est un entier relatif impair >= -1. Ce qui est intéressant dans cette forme c'est la division par 3. Puisque par exemple 2M - 1 est divisé par 3, ça veut dire que p1 est divisible par 3 si et seulement si 2M - 1 est divisible par 9. En calculant (3*suitePred(n,lg)) mod 9 on obtient la répartition des "mauvais prédécesseurs", ceux qui sont divisibles par 3. Exemple avec les 15 premiers prédécesseurs de n=5 :

0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6. Il existe donc 1/3 de mauvais prédécesseurs. Bien entendu, leur répartition varie selon la valeur de n. Avec (3*suitePred(11,15)) mod 9 on obtient 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, 0.

Il est à mon avis possible de construire un algorithme qui tiendrait compte de cette répartition et qui renverrait une suite de prédécesseurs dans laquelle aucun ne serait divisible par 3. Mais son coût en termes de calculs serait probablement plus élevé que le simple suitePred(n,lg,1), qui renvoie déjà ce type de suite. D'où l'intérêt d'un algorithme de construction de suites aléatoires par la fin, qui s'arrête dès que le nombre maximal de termes est atteint OU lorsque le dernier terme calculé est divisible par 3, c'est-à-dire dans un cas sur trois.

[Robot]

Il est à mon avis possible de construire un algorithme qui tiendrait compte de cette répartition et qui renverrait une suite de prédécesseurs dans laquelle aucun ne serait divisible par 3.

Bien sûr, j'ai déjà expliqué comment en long, en large et en travers. Il serait peut-être temps que tu t'en aperçoives. Et ça ne dépasse pas le niveau moyen d'un exercice de 3e année de licence de mathématiques.
Tout ça pour quoi ? Quelle avancée ? La première phrase de ton texte
"Dans ce qui suit je présente une solution au fameux problème proposé dans les années 1930 par le mathématicien allemand Lothar Collatz."
est une tromperie manifeste sur la marchandise.

[syrac]

Oui mais le problème avec toi c'est que tu n'apportes rien de concret. Tu dis "c'est déjà fait", "j'en ai déjà parlé", mais par exemple l'algorithme qui tient compte de la répartition des prédécesseurs divisibles par 3, que tu prétends avoir déjà expliqué, où diable est-il passé ?

Tu es un théoricien et moi un expérimentateur. Mes déductions sont basées sur l'expérimentation avant tout, si bien que lorsque je dis "voilà comment ça fonctionne", je le montre et je l'explique. Toi tu as déjà tout découvert mais ce qui est étonnant c'est qu'on n'a rien vu !

Quant à la tromperie, tu fais bien d'en parler. Je ne sais pas à quel document tu fais allusion, mais dans celui que j'ai posté en créant ce fil j'ai parlé d'une expression qui était toujours égale à 1, et qui est la preuve la plus solide qu'une suite de Collatz se termine toujours par 1. Pourquoi ne pas mettre tes connaissances en maths et tes talents au service de la démonstration de sa validité, plutôt que de perdre ton temps en critiques stériles ? C'est la raison de ma présence ici, trouver des gens capables de démontrer formellement ce que j'avance et proposer d'autres pistes, sans doute plus élaborées. Sinon je pourrais aussi bien faire ma petite salade dans mon coin.

[syrac]

@Robot

J'ajoute que je comprends ton approche du problème de la sélection des prédécesseurs non divisibles par 3. Ce que j'aimerais seulement savoir c'est comment tu la mets concrètement en oeuvre, à l'aide de n'importe quel langage de programmation. Parce que la théorie c'est bien, mais ce qu'on essaie de faire en ce moment c'est de trouver un moyen exploitable de construire une suite de Collatz par la fin, ce qui implique de passer à un moment donné à la pratique.

Et je crois que l'idéal serait de trouver une relation directe entre n et l'un quelconque de ses prédécesseurs non divisibles par 3, c'est-à-dire qui ne passe pas par des tests pour en sélectionner un au hasard. Or, jusqu'à preuve du contraire, personne ne sait encore le faire.

[Robot]

Quant à la tromperie, tu fais bien d'en parler. Je ne sais pas à quel document tu fais allusion.

Tu le sais très bien : c'est le document sur ton site .

Oui mais le problème avec toi c'est que tu n'apportes rien de concret. Tu dis "c'est déjà fait", "j'en ai déjà parlé", mais par exemple l'algorithme qui tient compte de la répartition des prédécesseurs divisibles par 3, que tu prétends avoir déjà expliqué, où diable est-il passé ?

Puisque tu sembles avoir des difficultés pour traduire les banalités que j'ai écrites en programme, je le fais pour toi. Je me contente de calculer la remontée "minimale" en choisissant à chaque fois le plus petit prédécesseur.

[syrac]

Tu le sais très bien : c'est le document sur ton site.

Eh bien ça prouve au moins que mon cerveau fume ! :we:

Rassures-toi, j'ai depuis abandonné cette approche...

Puisque tu sembles avoir des difficultés pour traduire les banalités que j'ai écrites en programme, je le fais pour toi. Je me contente de calculer la remontée "minimale" en choisissant à chaque fois le plus petit prédécesseur.

Le problème est que ton approche "minimaliste" ne te permet que de produire une seule suite, la même encore et toujours. Quel est l'intérêt ?

C'est précisément ce genre d'algorithme que j'espérais te voir afficher, parce que je me doutais bien qu'il serait beaucoup plus compliqué, puisqu'il comporte 6 tests, que le mien, qui lui produit des suites réellement quelconques avec un seul test.

[syrac]

Je ne sais pas quel langage tu as utilisé (en tout cas pas du C++) mais est-ce qu'il permet l'usage de tableaux indexés ?

table = (1 => 2, 2 => 1, 4 => 2, 5 => 3, 7 => 4, 8 => 1)
r = n%9
y = table(r)

Ou plus simple : y = table(n%9)

Ça évite d'avoir à faire des tests.

EDIT : le fait d'éviter les 6 tests rend cet algorithme nettement plus intéressant. Comment ferais-tu pour sélectionner un prédécesseur au hasard ?

[Ben314]

J'y crois pas !!!
Syrac qui demande quel et l'intérêt d'un algorithme !!! (je vous rassure tout de suite, c'est pas un des siens... :ptdr: )

[Robot]

J'utilise Sagemaths, qui est écrit en python, et j'en fais une utilisation rudimentaire.
Je ne vais pas perdre mon temps à optimiser ce que j'ai écrit, ni à introduire un choix aléatoire parmi les prédécesseurs. Tu peux le faire si ça t'amuse, j'ai complètement décrit les prédécesseurs possibles en fonction de la classe modulo 9.

Sur ce , la discussion tourne sérieusement en rond et j'ai des choses plus intéressantes à faire. Bon vent donc, et bien le bonjour de ma part aux extra-terrestres que tu rencontreras !