La conjecture de Collatz

Pourrais-tu me dire quel est le point commun entre ces 93 nombres ? Ceux que tu cites sont en gras.

316757, 320341, 320397, 329045, 329493, 329941, 329955, 330097, 330101, 333141, 334933, 334961, 336085, 336099, 336149, 336173, 336213, 336325, 336437, 336477, 336565, 336577, 339285, 339509, 339733, 339811, 339813, 342805, 342837, 342849, 342869, 342925, 342981, 343001, 343045, 343051, 345029, 345045, 345049, 345059, 345109, 345123, 345141, 345157, 345163, 345175, 345207, 364885, 364997, 365269, 365283, 365297, 365397, 365453, 365589, 365603, 365699, 365701, 366357, 366421, 366477, 366513, 366515, 366645, 366661, 366667, 366677, 366705, 366709, 366733, 366743, 366765, 366805, 366819, 366933, 367045, 367117, 367121, 367301, 367309, 367321, 367797, 367813, 367821, 367853, 367863, 368193, 368195, 368197, 368203, 368205, 368215, 368223

Plus simplement, ces 93 nombres constituent la liste exhaustive de tous les nombres impairs dont la suite compressée est de longueur 29 et de type 5 (il existe 5 termes impairs entre $n_0$ et 1). Leur longueur standard est 35 (c'est-à-dire 29 + 5 + 1).

Ta réponse montre la confusion dans laquelle tu te trouves vis-à-vis du problème de Collatz. Il te suffisait de calculer la longueur de chacune de ces suites pour comprendre ce qui les liait. Au lieu de ça tu as inventé un nouveau concept, i_source, censé expliquer ce que sont ces 93 nombres, mais qui ne fait qu'ajouter à la confusion.

PMF a écrit :
Nous pouvons observer que chaque suite a le même successeur impair dans la suite de Collatz que i_source.

Et tu n'en a même pas déduit ce qu'il y avait à en déduire, à savoir que 3, 13, 53, 213, 853, 3413, 13653, ... sont les prédécesseurs impairs de 5, raison pour laquelle ils ont tous 5 pour successeur impair.

C'est ça qui est tuant chez toi : tu fais tout un plat de quelque chose que des tas de gens savaient déjà. Sauf que eux ne sont pas allés le proclamer sur un forum comme étant la découverte du siècle.

Allez, cadeau pour la route : calcul des 9 premiers prédécesseurs d'un terme impair, en Python :

def preds(n):
	m = 3 - n % 3
	if m == 3:
		return "Multiple de 3"
	else:
		lst = []
		k = (n * 2**m - 1) // 3
		lst.append(k)
		for j in range(1, 9):
			k = 4 * k + 1
			lst.append(k)
	return lst

print(preds(5))

preds(5) renverra [3, 13, 53, 213, 853, 3413, 13653, 54613, 218453]

La première mention de l'entité i_source se trouve dans ce message. Sans aucune explication évidemment. Normal, si tu avais compris de quoi il s'agissait tu l'aurais probablement expliqué. Mais comme ce n'était pas le cas, tu t'es contenté du mot i_source.

Ce que tu appelles i_source est en fait "le plus petit prédécesseur impair d'un terme impair". Parmi l'infinité de ces prédécesseurs, le plus petit est le plus difficile à calculer. Prenons l'exemple de 35 et appelons la fonction ppp(35) (pour Plus Petit Prédécesseur) :

def ppp(n):
	m = 3 - n % 3
	if m == 3:
		return "Multiple de 3"		# un multiple de 3 n'a aucun prédécesseur
	else:
		return (n * 2**m - 1) // 3

print(ppp(35))

La fonction renverra 23, le fameux i_source, qui est le plus petit prédécesseur de 35.

On peut ensuite calculer par récurrence autant de prédécesseurs de 35 qu'on veut :

$p_{i+1}=4\,p_i+1$

Ce qui donne

4 * 23 + 1 = 93
4 * 93 + 1 = 373
etc.

PMF a écrit :
Il faut noter que des impairs ayant le même i_source partagent le même e avec des valeurs x incrémentées de 2

Au lieu de calculer les prédécesseurs par récurrence, on peut tout aussi bien faire

n = 35	# valeurs précédentes de n et m, ainsi que celle calculée du plus petit prédécesseur
m = 1
lst = [23]
for i in range(1, 9):
	m += 2
	lst.append((n * 2**m - 1) // 3)

print(lst)  # [23, 93, 373, 1493, 5973, 23893, 95573, 382293, 1529173]

On reprend la même formule que pour le calcul du plus petit prédécesseur, en incrémentant simplement $m$ de 2 à chaque itération. La méthode par récurrence est cependant plus rapide. Augmenter l'exposant $m$ de 2 implique que pour construire la suite du prédécesseur ainsi obtenu il faudra 2 divisions par 2 supplémentaires. Par exemple,

23, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1

93, 140, 70, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1

373, 560, 280, 140, 70, 35, 53, 80, 40, 20, 10, 5, 8, 4, 2, 1

On voit que pour atteindre 35 il faut 1, 3 puis 5 étapes. Et bien sûr, le nombre de termes impairs ($e$) dans chacune des suites est invariable (on ne fait qu'ajouter des termes pairs).

Il va sans dire que tu étais incapable de fournir la moindre explication à ces accroissements successifs de longueur. Tout ce que tu constates est que 93, 373, 1493, 5973, 23893, etc. "possèdent le même i_source" (sic) alors qu'en réalité le i_source en question fait partie de ces prédécesseurs, qu'il est le plus petit d'entre eux. Tout comme tu transformes la réalité en prétendant qu'une suite de longueur 30 est de longueur 29, tu la transformes de nouveau en inventant l'entité i_source dont tu décrètes l'existence indépendante, source de je ne sais quoi et très probablement brique fondamentale dans la démonstration de la conjecture.

Wilfrid a écrit :
Tu n'as pas défini j

Pas besoin, on peut faire ce calcul beaucoup plus simplement :

def successeur(n):
	m = 3 * n + 1
	n1 = m // (m & -m)
	m = 3 - n1 % 3
	return [n1, (n1 * 2**m - 1) // 3]


print(successeur(95573))  # Renvoie [35, 23]

La fonction "successeur(n)" renvoie "[successeur de n, le plus petit prédécesseur de celui-ci]".

Je ne vois pas ce que tu vas pouvoir en faire, mais c'est ton problème.

e = 4 ne veut rien dire en soi. Une suite de Collatz est définie par sa longueur et par le nombre de termes impairs qu'elle contient, ce que pour ma part je nomme $L$ et $t$ (pour "type"). Quant au concept de "plus petit prédécesseur de e = 4", aucune idée de ce que c'est. Si tu parles de toutes les suites comptant 4 termes impairs tu oublies une chose : puisque tu comptabilises $n_0$ dans ce nombre, lorsque tu le feras précéder de son plus petit prédécesseur tu te retrouveras avec une suite comptant 5 termes impairs au lieu de 4. Donc ça t'avancera à quoi puisque le sujet de l'étude se sera transformé ?

D'accord. Mais tu peux faire débuter tes suites par n'importe quel prédécesseur du second terme. Qu'est-ce ça changera que ce soit l'un ou l'autre ?

PMF a écrit :
Comme tu le vois ci dessus nous avons les suites se terminant par i=(2^(2n)-1)/3 avec n un entier positif.

Tu peux créer des suites se terminant par tout ce que tu veux, aucun problème. Il suffit de partir de ce dernier terme et de lui calculer autant de prédécesseurs que tu veux, que ce soit le plus petit ou non. Je suppose d'ailleurs que c'est ce que tu as fait.

Toutes les suites que tu peux imaginer existent, la preuve étant qu'à partir d'une suite aléatoire d'exposants de 2, de longueur arbitraire, chacun d'eux correspondant au nombre de divisions par 2 qu'on a effectué pour passer d'un terme impair au suivant, on peut retrouver son premier terme (j'en ai parlé quelque part il y a longtemps. L'algorithme est dû à Collag3n). Crois-moi, tu seras mort bien avant de parvenir à la moindre conclusion.

Voici l'algorithme conçu par Collag3n, bidouillé par moi-même et optimisé par GPT-4. La fonction suiteImpaire(n) est là uniquement pour calculer le dernier terme du segment de suite résultant :

"""
Suite de Collatz impaire
"""
def suiteImp(n):
	lst = [n]
	while n > 1:
		m = 3 * n + 1
		n = m // (m & -m)
		lst.append(n)

	return lst

"""
Renvoie les premier et dernier termes du segment de suite défini par une séquence d'exposants de 2
"""
def exp2n0(seq):
	s = seq.pop()
	n = (5**(s % 2) * 2**s - 1) // 3
	for u in reversed(seq):
		m = 5**(u % 2)
		inc = 2**(s + 1)
		while (n - m) % 6 != 0:
			n += inc
		n = (n * 2**u - 1) // 3
		s += u

	q = suiteImp(n)[:len(seq)+2][-1]
	print(f"{n} | {q}")
	return None


exp2n0([2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 2, 1, 2])  # Affiche 121 | 319

Avec la suite d'exposants fournie, exp2n0(seq) affiche 121 | 319. Le segment de suite correspondant est

121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319

On voit que le nombre de termes pairs situés entre deux termes impairs correspond exactement à la suite d'exposants. Quelle que soit la suite d'exposants, l'algorithme calculera le segment de suite auquel elle correspond. Donc toutes les suites existent, aucune ne fait exception. Chercher un ou des cas particuliers serait une perte de temps.

Wilfrid a écrit :
Ce qui m'intéresse est de savoir pourquoi le nombre de suites standard de longueur donnée est astronomiquement inférieur au nombre de suites compressées de la même longueur.

J'ai la réponse. Pour commencer je dois préciser que ma méthode de calcul du premier terme des suites de longueur donnée n'a rien à voir avec celle de PMF. Je ne m'intéresse qu'aux suites compressées et lui aux suites standard ; d'autre part, j'attribue un type aux suites, qui est le nombre de termes impairs qu'elles contiennent hormis $n_0$ (premier terme) et 1. PMF comptabilise tous les termes impairs sauf 1, le dernier. Enfin, la longueur d'une suite correspond pour moi à son nombre total de termes ; pour PMF, la longueur n'inclut pas 1 (?).

Pour transformer une suite compressée typée en suite standard on met tout simplement en œuvre la fonction de Collatz : si $n$ impair faire $3\,n+1$. C'est ce qu'on ajoute après chaque terme impair :

compressée : 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1
standard : 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Comme le nombre de termes impairs sans $n_0$ et 1 représente le type $t$ de la suite, la longueur $L'$ d'une suite standard est égale à celle d'une suite compressée augmentée de $t+1$ :

$L'=L+t+1$

+1 pour tenir compte du terme pair additionnel après $n_0$.

compressée : 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1
standard : 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

$L'=11+3+1=15$

Supposons que nous désirions trouver toutes les suites standard de longueur 25. Nous posons

$L+t+1=25$
$L+t=24$

$t$ ne peut pas être égal à 0 car il n'existe aucune suite compressée de longueur paire et de type 0 (les seuls termes impairs sont alors $n_0$ et 1).

• Nous commençons donc avec $t=1$, ce qui donne $L=23$. il existe 3 suites compressées de longueur 23 et de type 1 :
  464213, 466005, 466033.

• $t=2, L=22$. 8 suites :
  70997, 72789, 72817, 77141, 77365, 77589, 77667, 77669

• $t=3, L=21$. 10 suites :
  11605, 11829, 12053, 12131, 12133, 12853, 12885, 12893, 12913, 12931

• $t=4, L=20$. 9 suites :
  1877, 1933, 1969, 1971, 1989, 2009, 2141, 2147, 2149

• $t=5, L=19$. 4 suites :
  309, 321, 325, 331

• $t=6, L=18$. 2 suites :
  49, 51

On ne peut pas aller plus loin puisqu'il n'existe aucune suite compressée de longueur 17 et de type 7.

Au total nous avons donc 36 suites standard de longueur 25.

En comparaison, il existe 160 suites compressées de longueur 25. Plus $L$ augmente et plus la différence se creuse. C'est pourquoi j'ai toujours dit que mener une étude du problème de Collatz en se penchant sur les suites standard revient à se priver volontairement de la quasi totalité des données à notre disposition. Une sorte de hara-kiri.

PMF a écrit :
nous pouvons générer des suites d'étapes impaires uniques comme celles présentées ci-dessous :
11, 17, 13, 5
...

Uniques dans quel sens ? Chaque entier positif est unique dans l'arbre des suites de Collatz, donc la séquence 11, 17, 13, 5 l'est également puisque ses termes ne peuvent pas figurer ailleurs. On peut néanmoins s'intéresser aux exposants de 2 qui ont été produits lors de sa création : 1, 2, 3. Existe-t-il une autre séquence générant les mêmes exposants ? Oui, une infinité :

139, 209, 157, 59
267, 401, 301, 113
395, 593, 445, 167
523, 785, 589, 221
etc. etc.

Si tu en veux d'autres tu n'as qu'à demander. La différence entre ces séquences et celles que tu proposes est que le dernier terme de celles-ci figure parmi les prédécesseurs de 1 non-multiples de 3 : 5, 85, 341, 5461, 21845, ... , et que leur premier terme est le plus petit prédécesseur du second terme. Ces séquences que tu qualifies d'uniques je peux t'en fabriquer également à la pelle, puisqu'il en existe une infinité :

23, 35, 53, 5
6065, 4549, 853, 5
739, 1109, 13, 5
6067, 9101, 3413, 5
53024227, 79536341, 1864133, 349525
6628033, 4971025, 3728269, 1398101
565592395, 848388593, 636291445, 89478485
etc. etc.

Bref, il va falloir que tu trouves quelque chose de plus convaincant.

C'est GPT-4 qui t'a fourni cet algorithme ?

Ce qui est ennuyeux est qu'il renvoie toujours le plus petit prédécesseur. Le sommeil te guette avec ce genre de résultat. Ce qu'il faudrait c'est faire varier un peu ce qu'il renvoie en générant une liste des 6 plus petits prédécesseurs non-multiples de 3, par exemple, et en choisissant l'un d'eux au hasard.

Et une fois les résultats plus variés obtenus, c'est quoi la suite ?

[suite]

Pour le cas où tu ne serais pas convaincu, j'ai dit précédemment que lorsqu'on connaît le plus petit prédécesseur $p_0$ d'un terme impair on peut calculer les autres en faisant simplement $p_{i+1}=4\,p_i+1$. Ou encore, si on connaît l'un des prédécesseurs on peut revenir au plus petit en faisant $p_i=(p_{i+1}-1)/4$. On peut continuer aussi longtemps que le résultat est entier et impair.

Exemple : lorsque tu poses $n=37$ tu ne sais pas si 37 est le plus petit prédécesseur de son successeur. Tu peux alors calculer $(37-1)/4=9\,,$ puis $(9-1)/4=2$. Le plus petit prédécesseur est donc 9. Mais revenons à ta formule.

Lorsque $k=1$,

$n*2^{2\,(k - 1)} + (2^{2\,(k - 1)} - 1)/3=n$

Lorsque $k=2$,

$n*2^{2\,(k - 1)} + (2^{2\,(k - 1)} - 1)/3=4\,n+1$

Lorsque $k=3$,

$n*2^{2\,(k - 1)} + (2^{2\,(k - 1)} - 1)/3=4\,(4\,n+1)+1=16\,n+5$

etc.

C'est la même chose que $p_{i+1}=4\,p_i+1$. Ta formule calcule donc bien les prédécesseurs du successeur de i_source, y compris i_source lui-même, obtenu avec k = 1.