Olivier Pirson [OPi]

problème 3n + 1

[DS] [JF] [OPi]

“Mathematics is not yet ready for such problems.”
(Paul Erdős)


[xkcd - Collatz conjecture]
(xkcd)
n   si n est pair
Pour tout n naturel non nul on va itérer la fonction de Terras T(n) :=    2         [OEIS A014682, A070168]
3n + 1   si n est impair
    2    

Les premières itérations en commençant avec 1, 3, 6, 7, 9, 12 ou 15 donnent :
1 ‌→ 2 ‌→ 1 ‌→ …
3 ‌→ 5 ‌→ 8 ‌→ 4 ‌→ 2 ‌→ 1 ‌→ …
6 ‌→ 3 ‌→ 5 ‌→ 8 ‌→ 4 ‌→ 2 ‌→ 1 ‌→ …
7 ‌→ 11 ‌→ 17 ‌→ 26 ‌→ 13 ‌→ 20 ‌→ 10 ‌→ 5 ‌→ 8 ‌→ 4 ‌→ 2 ‌→ 1 ‌→ …
9 ‌→ 14 ‌→ 7 ‌→ 11 ‌→ 17 ‌→ 26 ‌→ 13 ‌→ 20 ‌→ 10 ‌→ 5 ‌→ 8 ‌→ 4 ‌→ 2 ‌→ 1 ‌→ …
12 ‌→ 6 ‌→ 3 ‌→ 5 ‌→ 8 ‌→ 4 ‌→ 2 ‌→ 1 ‌→ …
15 ‌→ 23 ‌→ 35 ‌→ 53 ‌→ 80 ‌→ 40 ‌→ 20 ‌→ 10 ‌→ 5 ‌→ 8 ‌→ 4 ‌→ 2 ‌→ 1 ‌→ …

Le constat est que pour tous les naturels non nuls que l’on a essayés, l’itération passe toujours par 1. Le problème 3n + 1 (aussi appelé problème ou conjecture 3x + 1, de Collatz, de Syracuse, de Kakutani…) est la conjecture que cela est vrai pour tout les naturels non nuls.

? ∀n ∈ ℕ*  : T(n) → 1 ?

Parcours des naturels jusque 100 (20 juin 2011) : [T_100.pdf].pdf (42,3 Kio) *  .svg (59,3 Kio)

 ∀α, k ∈ ℕ  : α:0…002 = α.2k  ‌→k  α    donc  ∀ k ∈ ℕ  : 10…002 = 2k  ‌→k  1 

 ∀α, k ∈ ℕ  : α:1…112 = α.2k + 2k - 1 = (α + 1).2k - 1  ‌→k  α:2…223 = α.3k + 3k - 1 = (α + 1).3k - 1 

n   si n est pair
Une variante équivalente est de considérer la fonction de Collatz C(n) :=    2         [OEIS A006370, A070165]
3n + 1   si n est impair

? ∀n ∈ ℕ*  : C(n) → 1 ?

Pour la fonction C(n), une étape impaire est toujours suivie d’une étape paire.
Alors que pour tout n naturel non nul : T(n) ≡ (n)1   [2]     (c.-à-d. que la parité de T(n) c’est le deuxième chiffre binaire de n).
Donc pour la fonction T(n), le dernier chiffre binaire est l’information "nécessaire et suffisante" pour savoir quelle opération est effectuée. C’est pourquoi je trouve qu’il faut privilégier cette fonction de Terras T(n), plutôt que la fonction de Collatz C(n).

Tables de quelques itérations pour ces deux fonctions (20 juin 2011) : [text].pdf (39,8 Kio) *  

Problèmes σimpair et GR :   [!!!]

Je conjecture, de façon similaire, que l’itération de la fonction σimpair (somme des diviseurs impairs, OEIS A000593) aboutit toujours à son unique point fixe 1 :

? ∀n ∈ ℕ*  : σimpair(n) → 1 ?

Vérifié (par calcul) pour les n ≤ 1 000 000

Parcours des naturels jusque 100 (20 juin 2011) : [sigma_odd_100.pdf].pdf (35,5 Kio) *  .svg (50,6 Kio)

(Si cette conjecture est vraie, alors on en déduit directement qu’il n’existe pas de nombre parfait impair.)

Je conjecture de même que l’itération de la fonction GR (nombre de représentations en somme de 4 carrés d’entiers, OEIS A000118) aboutit toujours à son unique point fixe 96 :

? ∀n ∈ ℕ : GR(n) → 96 ?

Vérifié (par calcul) pour les n ≤ 1 000 000

Parcours des naturels jusque 100 (20 juin 2011) : [GR_100.pdf].pdf (41,6 Kio) *  .svg (72,2 Kio)

∀n ∈ ℕ*  : GR(n) =   24 σimpair(n)   si n est pair
8 σimpair(n)   si n est impair

Voir Théologie grecque, Sommes et différences pp. 51 et 61.

Bien que ces deux dernières conjectures semblent intiment liées, je ne parviens pas à établir leur équivalence…
Il me semble de plus que leur difficulté, tout comme le problème 3n + 1, provient du "mélange de facteurs 2 et 3".


Quelques liens sur le problème 3n + 1 :
* Lecteur pdf : Adobe Reader
 Olivier Pirson [OPi] mardi 27 septembre 2016 [DS] [JF] [OPi]