Automate de Collatz – Règles simplifiées

Lien avec la conjecture de Collatz (ou de Syracuse)

• Décomposons un entier impair en somme de puissances de 2, par exemple $89 = 2^0+2^3+2^4+2^6$.
• Dans l'automate, la liste des exposants devient celle de la position de chaque pion relativement au premier, qui représente $2^0=1$ et assure ainsi de ne traiter qu'avec des entiers impairs : $[0, 3, 4, 6]$.
• Dans une suite de Collatz, le successeur impair de $89$ est $3 \times 89+1=268$, puis $268/2=134$, puis $134/2=67$. Il faut donc 3 itérations de l'algorithme de Collatz pour passer de $89$ à $67$, représenté par $[0,1,6]$.
• De son côté, l'automate transforme $[0, 3, 4, 6]$ en $[0,1,6]$ en une seule itération.

Une infinité de possibilités

État final

Liens

Représentation booléenne du voisinage d'un pion

def iterer(positions):
	"""
	Fonction destinée à l'automate utilisant les drapeaux gauche1/droite1
	(Vrai si voisin distant d'une cellule, Faux autrement).
	"""
	resultats = set()
	n = len(positions)

	for i in reversed(range(n)):	# on commence par le dernier pion
		pion = positions[i]
		# bord gauche : forcer True pour i == 0 (aucun voisin gauche), sinon test d'adjacence
		gauche1 = (i == 0) or (positions[i] - positions[i-1] == 1)
		# bord droit : forcer False pour i == n-1 (aucun voisin droite), sinon test d'adjacence.
		# Grâce au 'and', pas d’erreur pour i == n-1, le résultat sera Faux
		droite1 = (i < n-1) and (positions[i+1] - positions[i] == 1)
		
		if gauche1 and droite1: 			# cas V-V
			resultats.add(pion + 1)
		elif gauche1 and not droite1: 	# cas V-F
			cible = pion + 2
			while cible in resultats:
				resultats.discard(cible)
				cible += 1
			resultats.add(cible)
		elif not gauche1 and droite1: 	# cas F-V
			resultats.add(pion)
		else: 						# cas F-F
			resultats.update([pion, pion + 1])
	
	return sorted(resultats)

# Exemple d'entrée : positions = [0, 2, 12, 13, 15, 16] → 110597
# Résultat retourné : [0, 8, 12, 14] → 20737
# Dans une suite de Collatz, 20737 est bien le successeur impair de 110597
	

Un peu d'histoire

function transforme(S) {
	if (!Array.isArray(S)) return "Erreur";
	var L = S.length-1, b = false, c, d, i;

	// Insérer le nouveau terme S[L]+1 à l'indice L+1.
	function inserNouv() {
		if (!b) S.splice(L+1,0,S[L]+1);
	}

	// Règles 1 et 2.

	while (L > 1) {
		if (S[L] - S[L-1] == 1) {
			S[L] += (b ? 1 : 2); // b true ? oui, ajouter 1 : non, ajouter 2
			b = true
		} else {
			inserNouv();
			b = false
		}
		L--
	}

	inserNouv(); // L = 1, indice non traité par la boucle (non prise en compte de m = min(S)).

	// Règle 3. m = m+2, puis vérifier que min(S) est bien au début de la liste.
	// Si ce n'est pas le cas il est en seconde position --> inverser les 2 premiers termes.
	
	S[0] += 2;
	if (S[0] > S[1]) {
		[S[0],S[1]] = [S[1],S[0]]
	}

	// Règle 4. Suppression des doublons. Deux termes identiques étant toujours consécutifs,
	// leur différence est 0.

	d = S.slice(1).map((x,i) => x-S[i]); // Différences entre les termes de S.
	b = true;
	while (b) {
		i = d.lastIndexOf(0); // Indice du dernier 0 dans d. Renvoie -1 si aucun 0.
		if (i !== -1) {
			d.splice(i,1); // Supprimer ce 0
			// On boucle parce que les doublons peuvent être chaînés.
			c = true;
			while (c) {
				if (S[i] == S[i+1]) {
					S.splice(i,1); // Supprimer le terme de S à la position i.
					S[i]++ // Le terme suivant prend sa place. L'incrémenter.
				} else c = false
			}
		} else b = false
	}

	return S
}

// Soustraction de la valeur du premier terme (le minimum) de tous les termes
function reduire(arr) {
	const min = Math.min(...arr);
	return arr.map(v => v - min);
}

// Le paramètre de la fonction transforme est une liste triée d'au moins deux entiers naturels,
// tous distincts, le premier étant toujours 0. Voici un exemple :

console.log(reduire(transforme([0, 2, 12, 13, 15, 16])));
// Tout comme la fonction Python ci-dessus, affiche [0, 8, 12, 14]

Conclusion