problème 3n + 1 et problèmes σimpair, ς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 (sigmaimpair) et ςimpair (varsigmaimpair)

Je conjecture, de façon assez 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,1 × 1011 ≃ 1,6 × 236

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.)

[varsigma_odd 1001 odd circular]
Impairs jusque 1001
.pdf (72,5 Kio)
.svg (277,1 Kio)

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

Je définis la fonction ςimpair telle que ∀n ∈ ℕ* : ςimpair(n) = σimpair(n)/2k avec k la plus grande valeur telle que 2k divise impair(n). Ce qui conduit à la conjecture suivante, évidemment équivalente :

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

Parcours des naturels impairs jusque 101 (9 février 2019) : [varsigma_odd 101 odd] (9,8 Kio).svg (28,9 Kio)

Problème r4

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 p. 61.

Bien que ces dernières conjectures semblent fortement liées, je ne parviens pas à établir leur équivalence…

Quelques liens sur le problème 3n + 1