Bonjour à tous !

J'ai récemment pratiqué de l'Ocaml, et j'ai implémenté une fonction dont le résultat sera toujours 1.

Voici la définition de cette fonction :

Pour tout entier n strictement positif :
F (n) =
| si n = 1 => 1
| si n pair => F (n/2)
| si n impair => F (3*n + 1)

J'ai donc été assez étonné de voir que cette fonction ne rentrait jamais dans une boucle infinie.

J'ai donc élaboré quelques conjectures, effectué quelques calculs, et je me suis décidé de démontrer le résultat.

Cependant, la démonstration que j'ai faite repose sur des méthodes que je n'ai pas encore très bien assimilées (cf la récurrence forte), par conséquent, je ne sais pas si cette démonstration est correcte.
J'en fais donc appel à vos jugements.

Proposition :
Pour tout n strictement positif, F(n) = 1

Preuve :

Soit P1 la propriété : "Pour tout n pair strictement positif, F(n) = 1"

Pour n = 2 :
il existe k tel que n = 2k (k=1)
donc 2 est pair
donc F (2) = F (1) = 1
Donc P1 (2) est vraie

Prenons n un entier pair fixé
Supposons que, pour tout entier k tel que 2 <= k <= n, P1 (k) vraie
Il existe p tel que n = 2p (car n est pair)
donc F (n) = F (2p) = F (p)
or, n strictement positif, donc p >= 1
si p = 1, F (p) = 1 donc F (n) = 1
si p >= 2, n = 2p donc 2 <= p <= n
donc, par hypothèse de récurrence, F (p) est vraie
Donc, si pour tout entier k tel que 2 <= k <= n, P1 (k) vraie, alors P1 (n + 2) vraie

Donc, pour tout entier n pair, P1 (n) = 1

Soit n un nombre impair positif, alors il existe un entier k tel que n = 2k + 1
ainsi, F (n) = F (2k + 1) = F (6k + 4)
or, 6k + 4 = 2 (3k + 2) = 2 K avec K = 3k + 2, entier
donc 6k + 4 pair
or, pout tout entier m pair strictement positif, F (m) = 1
donc F (6k + 4) = 1
Donc pour tout nombre impair positif n, P1 (n) = 1

Donc pour tout entier strictement positif, P1 (n) = 1

CQFD ╬

J'attends vos commentaires avisés et vos remarques pertinentes.

Ta récurrence est fausse.
Tu ne peux pas affirmer que c'est vrai pour tout nombre n pair en ayant fait l'hypothèse de récurrence que c'est vrai pour tout entier < n, car ça inclut les impairs plus petits que n pour lesquels tu n'as rien montré du tout.

Je ne voudrais pas casser tes espoirs, mais il y a vraiment peu de chance que tu parviennes à démontrer ça puisqu'à ce jour aucun mathématicien n'y est parvenu, et c'est pourtant un vieux problème (près d'un siècle) portant le nom de Conjecture de Syracuse.

Ah ouais carrément xD
D'accord je m'écrases LOL.

Je viens de comprendre le gros problème de ma récurrence, ça ne marche que si p est lui-même pair, autrement dit si 2p congru à 0 modulo 4.

Pendant un instant j'y ai cru...

En fait KateVoegele42, tu l'as prouvé en faisant ça pour toutes les puissances de 2. Mais c'était trivial...

@Caduchon: Il y a encore des mathématiciens qui cherchent à le prouver ou ca ne presente pas d'interet de le faire ? Si c'est le cas, la recherche en est ou, prouver que c'est vraie, que c'est faux, que c'est pas démontrable ?

Je suis certain qu'il y en a qui cherchent encore. Ils ont testé par ordinateur les possibilités jusque <math>\(2^{62}\)</math> en 2008. Donc oui, il y a des chercheurs qui bossent sur ce problème.

J'espère que quelqu'un pourra un jour le démontrer !

Quelqu'un, ou, à défaut, quelque chose, si les ordinateurs finissent par nous rattraper.

@Freedom : ce document présente une bibliographie très étoffée des différents travaux autour de la conjecture de Syracuse.

N.B. : la terminologie anglaise la plus utilisée pour ce problème est "Collatz problem", pour ceux qui voudraient faire quelques recherches.