Enigme Un bout de Syracuse @ Prise2Tete

Clydevil · #1

Hello!

Le fameux problème de la conjecture de Syracuse.

Je rappelle brièvement la conjecture:
Prenez n'importe quel N entier puis appliquer la procédure suivante en boucle:
-Si ce que vous avez est pair appliquez l’opération T0 = x -> x/2 (vous divisez par deux)
-Si ce que vous avez est impair appliquez l’opération T1 = x -> (3x+1)/2 (vous multipliez par 3, ajoutez 1 et divisez deux)
La conjecture dit que vous finirez par toucher 1 quelque soit l'entier de depart.

La question que je vous pose:
Considérons une suite finie des opérations de base, par exemple: T0, T1, T0, T1, T1, T1, T0 existe t il toujours un N de départ dont les itérations commencent par cette suite d’opérations?

Bonne chance!

Vasimolo · #2

Bonsoir

La réponse est oui et d'une infinité de façons . J'avais passé un petit moment là-dessus il y a quelques années

Vasimolo

caduk · #3

Bonjour,
notons u_n(k) la n-ième valeur prise par k en suivant la suite de syracuse.
on a par exemple u_0(5) = 5, u_1(5) = 8, u_2(5) = 4 ...
montrons que les n premières étapes de la suite de Syracuse sont communes pour k et k+2^n, et que la n+1 étape diffère:
on montre aisément par récurrence que u_i(k+2^n) = u_i(k) + 2^(n-i)*p tant que i est inférieur à n, ou p est un nombre impair (plus précisément une puissance de 3), et on à bien à chaque étape la même parité entre u_i(k+2^n) et u_i(k)
à partir de i = n, la parité n'est plus la même, la prochaine étape sera donc différente.

On peut désormais construire notre nombre simplement, un exemple sur la méthode vaudra mieux qu'un long discours:
Notons + pour T1 et - pour T2
cherchons tout les nombres commençant par la séquence d'opérations:
- - - + - + + -
0 suit la séquence - - - - - - ...
0 + 2^3 = 8 suit la séquence - - - + - + - + - ...
8 + 2^6 = 72 suit la séquence - - - + - + + + - - - ...
72 + 2^7 = 200 commence par - - - + - + + -
L'ensemble des nombres commençant par cette séquence sont tout les nombres de la forme 200 + k*2^8
En effet, à partir du lemme démontrer plus haut, on démontre très facilement que les 2^n premiers entiers ont leur n premières opérations distinctes deux à deux.

Application:
-1 donne les opérations + + + + + + ...
2^n - 1 commencera donc par n fois l'opération +

nodgim · #4

La réponse est oui, pour n'importe quelle suite finie. Je te dis ça de mémoire sans aucune hésitation. La preuve est simple.

Cette séquence est compatible avec tous les nombres de la forme 128n + 18, et seulement eux.

Bastidol · #5

Bonjour,

Considérons seulement les 3 premières itérations :
N est pair
Exécutons T0 N/2 doit être impair possible
Exécutons T1 : (3N+2)/4 doit être pair possible
Exécutons T0: 3(N/2)+1 doit être impair impossible car 3 fois le nombre impair N/2 est impair + 1 est pair.

Je suis surpris de démontrer aussi facilement que cette suite est impossible.
Je me plante certainement

Ebichu · #6

Salut Clydevil, la réponse est oui !

Pour une suite de k opérations, l'astuce est de considérer les k derniers chiffres de la représentation binaire de N : chacune des 2^k possibilités pour ces chiffres correspond à une unique suite de k opérations parmi les 2^k suites possibles.

On peut le démontrer par récurrence sur k. Voici le point clé : si N1 et N2 terminent par les mêmes k bits et diffèrent par le (k+1)-ème bit, alors les k premières opérations issues de N1 et N2 sont identiques, et la (k+1)-ème opération diffère.

Par exemple :
...1011 donne ...001, puis ...10, puis ...1, puis ... via T1,T1,T0,T1.
...0011 donne ...101, puis ...00, puis ...0, puis ... via T1,T1,T0,T0.
On voit qu'à chaque étape, seul le bit de gauche est différent, et cette propriété est conservée jusqu'à la fin, donc seule la dernière opération diffère. C'est évident pour une opération de type T0, car on enlève juste un 0 à droite du nombre. Ça l'est moins pour une opération de type T1, mais ça s'explique en remarquant que 3*N + 1 = N + 2*N + 1 : si N1 et N2 ne diffèrent qu'à partir du k-ième chiffre, alors les k premiers chiffres de 2*N1 et 2*N2 sont identiques.

Franky1103 · #7

Je pense que répondre à ta question est équivalent à démontrer la conjecture elle-même. Bon courage.

Clydevil · #8

@Bastidol: La question porte sur n'importe quelle suite, mais même pour celle donnée en exemple en effet il y a qq chose de louche dans ta démo
@Franky1103: Nope c'est beaucoup plus simple

Bastidol · #9

j'ai trouvé ce qui cloche ((3N+2)/2 )/2 = (3N+2)/4

nodgim · #10

J'avais un temps utilisé ce procédé pour trouver le plus petit nombre d'une boucle éventuelle. J'avais alors identifié 38 nombres sur 512. Si le ratio 38/512 tend vers 0 au fur et à mesure qu'on va analyser , le nombre de survivants croît cependant presque exponentiellement. Ces données peuvent éventuellement aider à tester le plus grand nombre possible, en éliminant tous les autres.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 27-10-2017 17:11:41

Un boout de Syracuse

#0 Pub

#2 - 27-10-2017 18:22:02

un vout de syracuse

#3 - 27-10-2017 21:29:17

Un bout de Syacuse

#4 - 28-10-2017 08:03:28

un bout de syracise

#5 - 29-10-2017 11:41:39

un bout de syracusr

#6 - 29-10-2017 22:26:51

Un bout de SSyracuse

#7 - 30-10-2017 07:18:17

nU bout de Syracuse

#8 - 30-10-2017 10:11:26

Un bout dee Syracuse

#9 - 30-10-2017 18:10:07

Un bou tde Syracuse

#10 - 31-10-2017 07:43:25

Un botu de Syracuse

Réponse rapide

Sujets similaires

Pied de page des forums