Sergey Zhestkov, conférencier au MIPT et en parallèle expert OTUS, invite tout le monde à une leçon de démonstration gratuite du cours avancé "Mathématiques pour la science des données" , sur le thème: "Les cartes, leur matrice et leur diagonalisation" .
Et nous partageons traditionnellement avec vous la traduction de documents intéressants.
Malgré des sympathies récentes avec la tristement célèbre hypothèse de Collatz, nous ne pouvons toujours pas comprendre si un nombre peut sortir d'une boucle infinie.
Cet article est accompagné d'un avertissement: n'essayez pas de résoudre ce problème mathématique.
Vous serez tenté de l'essayer. Ce problème est formulé tout simplement, compréhensible et trop tentant. Choisissez simplement un nombre, n'importe quel nombre: si le nombre est pair, divisez-le en deux; si c'est impair, multipliez-le par 3 et ajoutez 1. Prenez le nouveau nombre résultant et répétez ce processus encore et encore. Si vous continuez à parcourir ces itérations un nombre suffisant de fois, vous vous retrouverez coincé dans une boucle infinie. Du moins nous le pensons.
, , 10: 10 - , 5. 5 - , 3 1. 16, , 2 8, 8 4, 2, , 1. 1 , 1. 4, , : 4 2, 1, 4, . .
11: , 1. 34, , 17, 1, 52, , 26, , 13, 1, 40, , 20, 10, 5, 1, 16, , 8, 4, 2 1. .
, , . , , : , . , , .
, . , . : , - , , , . , .
, :
(even - , odd - )
«» : n , , n . f , : , f (10) = 10/2 = 5, 10 , f (5) = 3 × 5 + 1 = 16, 5 . 3n + 1.
«» f. - , , - , . «» . 10 f, :
f (10) = 10/2 = 5
f (5) = 3 × 5 + 1 = 16
f (16) = 16/2 = 8
f (8) = 8/2 = 4
. 10 f:
10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …
, 1 → 4 → 2 → 1 →….
, 11 f
11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → ….
. , , 4 → 2 → 1 →…. 9 19 , , 27. , 111 .
, f 1. , 26⁸. , , 300 . ( !)
, : , 1. , , ℊ.
ℊ f, 1 , . ℊ f , . , 10 11 ℊ:
10 → 5 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …
11 → 12 → 6 → 3 → 4 → 2 → 1 → 2 → 1→ 2 → …
, 11 1 ℊ, f. 27 1 ℊ.
27 → 28 → 14 → 7 → 8 → 4 → 2 → 1 → 2 → …
ℊ , f, :
→ 2 → 1 → 2 → 1 → ….
, ℊ 1. «», n + 1. , , , - - 26⁸ - , . , . .
-, , . , n , ℊ(n) = n/ 2 < n. , , .
, n , ℊ(n) = n + 1, n. , + 1 , : ℊ + 1 . n :
,
.
- ,
, n. , > 1,
, ℊ 1, . : , , . - 1 . 1, , .
? .
ℊ, f . ℊ, f , , , : f . f, n :
. , n:
, n. , , . .
- , , , , : , , 1? , , , , : ,
.
, 3n + 1 . 3n + 1 4,
, . 3n + 1 4,
, . , , , .
. , 50%
,
. n > 1 , n, . 50%- ,
, , 25%- , . . , , . , , . , .
, « » . , , , , , 1, , , . 1976 - , , . , , , - , 1.
,
,
( n), f(n), f(x) - , , , . , , . , , « .»
. , . , : .
1. , , 1.
2. « » n - , , n 1. , 10 6, 11 14. 5.
3. :
, 1 → 2 → 1 → 2 → 1… . ?
, 1:
, 1. ,
, , 1.
, 2:
2^5 5,
…. 2^4 4, , 2^4, 5. , 5 → 16 → 8 → 4 → 2 → 1. ?
, 3:
:
5 → 14 → 7 → 20 → 10 → 5 → …
17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17 → …