problème 3n + 1, et σimpair, r4

Mathematics is not yet ready for such problems.

(Paul Erdős)

[xkcd - Collatz conjecture]
(xkcd)

Problème 3n + 1

Pour tout n naturel non nul on va itérer la fonction de Terras @@\DeclareMathOperator{\assign}{\,\mbox{$:=$}\,}% \mathbf{T(n)} \assign \left\{ \begin{array}{@{}l@{\quad}l@{}} \frac{n}{2} & \text{si }n\text{ est pair}\\ \frac{3n + 1}{2} & \text{si }n\text{ est impair}\\ \end{array}\right.@@ [OEIS A014682, A070168]

Les premières itérations en commençant avec 1, 3, 6, 7, 9, 12 ou 15 donnent :
121 → …
358421 → …
6 → 3 → 5 → 8 → 4 → 21 → …
7111726132010 → 5 → 8 → 4 → 21 → …
914 → 7 → 11 → 17 → 26 → 13 → 20 → 10 → 5 → 8 → 4 → 21 → …
12 → 6 → 3 → 5 → 8 → 4 → 21 → …
15233553804020 → 10 → 5 → 8 → 4 → 21 → …

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] (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

Une variante équivalente est de considérer la fonction de Collatz @@\mathbf{C(n)} \assign \left\{ \begin{array}{@{}l@{\quad}l@{}} \frac{n}{2} & \text{si }n\text{ est pair}\\ 3n + 1 & \text{si }n\text{ est impair}\\ \end{array}\right.@@ [OEIS A006370, A070165]

? ∀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) : PDF (39,8 Kio)

Problèmes σimpair et r4

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 ≤ 5 000 000 000

Parcours des naturels jusque 100 (20 juin 2011) : [sigma_odd 100] (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 r4 (ou GR, nombre de représentations en somme de 4 carrés d’entiers, OEIS A000118) aboutit toujours à son unique point fixe 96 :

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

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

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

@@ \forall n \in \mathbb{N}_{\star} : r_4(n) \assign \left\{ \begin{array}{@{}r@{\quad}l@{}} 24\,\sigma_{\text{impair}}(n) & \text{si }n\text{ est pair}\\ 8\,\sigma_{\text{impair}}(n) & \text{si }n\text{ est impair}\\ \end{array}\right.@@

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