[PowerShell] Calculer la conjecture de Syracuse

Pendant les fêtes un ami m'a parlé de la conjecture de Syracuse, en voyant la simplicité des opérations j'ai eu envie de faire un script pour calculer cette suite.

Conjecture de Syracuse : Qu'est ce que c'est?

C'est une suite mathématiques inventé par Lothat Collatz, on part d'un nombre entier strictement positif, si ce nombre est pair on le divise par 2, si ce nombre est impair on le multiplie par 3 et on ajoute 1. Puis on répète l'opération avec le résultat obtenu.

On obtient ainsi une suite d'entiers strictement positifs dont chacun dépend de son prédécesseur.

Si l'on part du nombre 10 en suivant la méthode de calcul décrite ci-dessus, on construit la suite 10, 5, 16, 8, 4, 2, 1, ...

La grande particularité de la conjecture de Syracuse c'est qu'une fois le chiffre 1 atteint, la suite se répète à l'infini en 1, 4, 2, 1, 4, 2, ... Et ce, à priori (ce n'est pas pour rien qu'on l'appelle conjecture), quelque soit le nombre de départ tant qu'il est entier strictement positif.

Malheureusement ou heureusement, l'infini étant une notion mathématique, il sera toujours impossible de prouver cette conjecture par le calcul de chaque nombre entier strictement positif.

Impossible, mais on peut quand même "s'amuser" à le calculer.

Le script complet

Le script sur GitHub

Les explications

Tout d'abord je vais avoir besoin d'une fonction que j'appellerai à l'intérieur d'elle même pour la rendre récursive:

Function Calc ($number) {

Ensuite il détecter si le nombre est pair ou impair, j'applique pour cela un modulo 2, sur le nombre.

Le modulo est tout simplement le reste d'une division euclidienne (vous savez celle que l'on découvre en primaire).

Par exemple pour obtenir 10 modulo 2 :

On divise 10 par 2, ce qui donne un quotient de 5 (le résultat de la division) et un reste de 0.

La division par 2 de n'importe quel nombre donnera toujours un reste égal à 0 ou 1, 0 pour les nombres pairs et 1 pour les nombres impairs.

Je teste donc le modulo 2 du nombre pour savoir si il est pair (si le résultat est égal à 0, il est pair), dans ce cas je divise le nombre par 2 et j'ajoute le résultat de mon calcul dans mon tableau pour le stocker:

	if ($number % 2 -eq 0){
	$result = $number / 2
	[void]$myArray.Add($result)

Autrement si le chiffre n'est pas pair, c'est qu'il est impair, dans ce cas je le multiplie par 3 et j'ajoute 1, puis également j'ajoute le résultat de mon calcul à la suite:

}Else{	
$result = $number * 3 + 1
[void]$myArray.Add($result)
} 

Nous avons vu un peu plus haut qu'une le résultat 1 obtenu la suite se répète à l'infini sous le format 1, 4, 2, … Je veux donc arrêter mon calcul une fois que le chiffre 1 est atteint dans les résultats. Pour ça c'est très simple il suffit de rappeler la fonction à l'intérieur d'elle même tant que le résultat est différent de 1 :

if ($result-ne1){				
Calc $result

Quand le résultat arrive à 1, j'écris sur la console que le chiffre 1 est atteint :

}Else{
write-host"Number 1 is reached"

Puis j'affiche les résultats de mon tableau :

write-host "List of steps : "
$myarray

Je mesure le "temps de vol", c'est à dire le nombre d'opération pour arriver à 1 et je l'affiche:

$flighttime = $myarray.Count
write-host "Flight Time = " $flighttime

Enfin je mesure le résultat le plus haut obtenu dans la suite et je l'affiche :

$max = $myarray | measure -Maximum
write-host "Maximum altitude : " $max.maximum
write-host ""				
}
}

Voilà notre fonction est prête à calculer la conjecture de Syracuse. Maintenant il nous faut des chiffres/nombres à analyser, de 1 à 10 pour commencer :

$numbers = 1..10

Pour lancer la fonction sur chacun de ces chiffres/nombres nous allons utiliser une boucle foreach :

foreach ($number in $numbers) {

On créé un tableau pour chacun de ces chiffres/nombres, et on affiche quel nombre va être calculé (en vert pour bien le voir) :

$myarray = [System.Collections.ArrayList]::new()
write-host -f green "Start calculus with number : " $number

Pour finir, on lance la fonction créée précédemment avec le nombre comme point de départ :

Calc $number
}

Si vous lancer ce script vous deviez obtenir le résultat ci-dessous, détaillant vos résultats concernant la suite de Syracuse :