Collatz Syracuse et Higman

[sergeburckel]

Je vous propose la chose suivante :

on écrit un nombre impair N en base 4 suivi par un # puis en base 7.

On remarque que si on fait la même chose pour les itérés M impairs de N, la suite de N n'est jamais une sous-suite de la suite pour M au sens où abc est sous-suite de xayubztcuvw


D'après un Théorème sur les mots de Higman, dans toute suite infinie :

w_1,w_2,w_3,...il existe forcément i<j avec w_i sous-suite de w_j.

Ici cela semble ne jamais être le cas...donc la suite est finie et la conjecture serait prouvée.

Cela marche aussi pour les bi-bases

[5, 7], [5, 9], [7, 8], [7, 9], [7, 10], [8, 10]

J'explique le sens de mettre un # :

Si tout le mot pour N est sous-suite du mot pour l'itéré M alors

N écrit en Base 4 est sous-suite d'un itéré M écrit en base 4 ET
N écrit en base 7 est sous-suite de M écrit en base 7.


à étudier.....

[sergeburckel]

Il semble que si on se restreint à la base simple B=331, la propriété est encore vérifiée.

C'est vrai au moins jusqu'à N=357 millions 1

Je répète l'idée, l'écriture en base B de N semble ne jamais être sous-suite de l'écriture en base B des itérés impairs de N par la fonction de Collatz.

à voir....

[sergeburckel]

vrai encore jusqu'à N=7000001

[bolza]

Bonjour,

tu pourrais donner un exemple avec des nombres concrets ?

parce que là je ne suis pas sur de tout comprendre :/
tu parle des base 4 et 7 ensuite dans ton deuxième poste tu parles
des bases "simple" 331 et 229 O_o

qu'est-ce que tu appelle précisément un "itérée" ??

[sergeburckel]

Pour la base 331, je ne suis sûr de rien, je teste...pour l'instant c'est vrai jusqu'à plus de 50 millions.

Soit la fonction F qui prend un entier impair N, le multiplie par 3 et ajoute 1, puis divise par 2 le résultat jusqu'à réobtenir un entier impair. Les itérés de N sont les F(N),F(F(N)),...si la conjecture est vraie on termine par 1.

Exemple :
L'écriture en base 4 de 27 est [1,2,3]
L'écriture en base 7 de 27 est [3,6]

F(27)=41

L'écriture en base 4 de 41 est [2,2,1]
L'écriture en base 7 de 41 est [5,6]

[1,2,3] n'est pas sous-suite de [2,2,1] ET [3,6] n'est pas sous-suite de [5,6]

Remarque que le OU suffit.

Je rappelle la notion de sous-suite par un exemple :

XYZX est sous-suite de aXbcYaaefZdX

car on peut retrouver les chiffres de XYZX dans le même ordre dans aXbcYaaefZdX.

Voilà.


PS : 50000001 écrit en base 331 donne : [1, 125, 121, 134].

Je n'y crois moins que pour la bibase (4,7) car avec la base 331, c'est plus une question de probabilité faible d'avoir des sous-suites.

[nodjim]

ça me semble bizarre cette conjecture. As tu bien conscience qu'une infinité de nombres donnent 2^n par la suite de Syracuse ? C'est à dire qu'on peut tomber sur un F(F(F(F....(N))..)=1. Et ce serait étonnant que 1 ne soit pas une sous suite d'un terme de F(F(F....))). En n'importe quelle base.
Bon, maintenant, je n'ai peut être pas bien compris ton idée...

[sergeburckel]

Nodjim, suivant la définition, quand on arrive à 1, on reste à 1 car F(1)=1.

On ne prend pas en compte cette singularité dans les énoncés car la conjecture dit : on finit par arriver à 1...après on boucle (et on se la boucle). La conjecture dit que c'est le seul cycle.

[sergeburckel]

Bolza, tu as raison....un 229 trainait encore là. C'est B=331.

désolé pour la coquille

[sergeburckel]

Bonjour,

tu pourrais donner un exemple avec des nombres concrets ?

parce que là je ne suis pas sur de tout comprendre :/
tu parle des base 4 et 7 ensuite dans ton deuxième poste tu parles
des bases "simple" 331 et 229 O_o

qu'est-ce que tu appelle précisément un "itérée" ??

désolé...le 229 était une coquille, c'est toujours 331.

[bolza]

à mon avis ça ne reste pas simple ^^

déjà exprimer le fait d'être une sous suite ne peut pas se traduire simplement
par une relation arithmétique, ensuite comme tu le faisais remarquer, c'est surtout une question
de probabilité :
le fait d'utiliser deux base, complique un peu le fait de trouver une sous suite.
Si tu faisais la même chose avec trois bases, tu réduirait encore considérablement les chances.

Malgré cela, en théorie, on peut faire des suites de collatz de longueur aussi grande que
l'on veut, donc qui nous dis que si on ne choisit pas une suite assez grande, on ne va pas finir par
trouver une sous-suite ?

Bref, ça reste un problème très compliquer ^^'

Ensuite, si on arrivait à montrer ton résultat, on aurait prouver que l'algorithme termine toujours,
mais pas qu'il termine forcément sur le même cycle ^^ (mais bon, ce serait déjà un bon début

[sergeburckel]

oui Bolza, cependant cela sent la possibilité de faire des inductions...non ?