Résolution de la conjecture Collatz et problème de Syracuse

"""#python
Bonjour, c'est Bing. Je peux vous aider à trouver des informations sur les nombres pairs et impairs. 😊

Vous avez décrit une règle qui s'applique aux nombres entiers. Pour un nombre pair, on le divise par deux.
Pour un nombre impair, on le multiplie par trois et on ajoute un. Par exemple :

- Si le nombre est 4, il est pair, donc on le divise par deux : 4 / 2 = 2
- Si le nombre est 5, il est impair, donc on le multiplie par trois et on ajoute un : 5 x 3 + 1 = 16

Cette règle est connue sous le nom de **conjecture de Collatz** ou de **problème de Syracuse**.
C'est un problème mathématique qui n'a pas encore été résolu.
Il consiste à se demander si, en appliquant cette règle à n'importe quel nombre entier positif,
on finit toujours par obtenir 1.

Par exemple, si on part de 6, on obtient la suite suivante :

- 6 est pair, donc on le divise par deux : 6 / 2 = 3
- 3 est impair, donc on le multiplie par trois et on ajoute un : 3 x 3 + 1 = 10
- 10 est pair, donc on le divise par deux : 10 / 2 = 5
- 5 est impair, donc on le multiplie par trois et on ajoute un : 5 x 3 + 1 = 16
- 16 est pair, donc on le divise par deux : 16 / 2 = 8
- 8 est pair, donc on le divise par deux : 8 / 2 = 4
- 4 est pair, donc on le divise par deux : 4 / 2 = 2
- 2 est pair, donc on le divise par deux : 2 / 2 = **1**

On a obtenu **1** au bout de **8** étapes. On dit que le temps de vol de **6** est de **8**.

La conjecture de Collatz affirme que pour tout nombre entier positif,
il existe un temps de vol fini qui permet d'obtenir **1**.
Mais personne n'a réussi à le démontrer ni à le réfuter.

Trouvez-vous ce problème intéressant ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import time

def long_func():
    start = time.perf_counter()
    for i in range(2, 1000001):
        while 1:
            if i == 1:
                break
            if i % 2:
                i = i * 3 + 1
            else:
                i /= 2
    end = time.perf_counter()
    print("long_func done at: %s sec." %(end-start))

def short_func():
    start = time.perf_counter()
    for i in range(2, 1000001):
        while 1:
            if i == 1:
                break
            if i & 1:
                i = i * 3 + 1
            else:
                i >>= 1
    end = time.perf_counter()
    print("short_func done at: %s sec." %(end-start))

long_func()
short_func()

1
2
3
4
5
6
7
8
9
10
11
12
def slowh_func():
    start = time.perf_counter()
    n = 100001
    while n > 1:  # n réduction.
        print(n)
        if not (n%6)%2:
            n //= 2
        else:
            n = n*3+1
    end = time.perf_counter()
    print("slowh_func done at: %s sec." %(end-start))

1
2
3
4
5
6
7
8
9
10
11
12
##############################################################################
def nb2(n):
    """Calcule le nombre de fois qu'on peut diviser n par 2
    """
    c = 0 # compteur
    while True:
        if n%2==0:
            c += 1
            n //= 2
        else:
            break
    return c

1
2
3
for i in range(1, 100, 2):
    j = i*3+1
    print(i, j, nb2(j))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
1 4 2
3 10 1
5 16 4
7 22 1
9 28 2
11 34 1
13 40 3
15 46 1
17 52 2
19 58 1
21 64 6
23 70 1
25 76 2
27 82 1
29 88 3
31 94 1
33 100 2
35 106 1
37 112 4
39 118 1
41 124 2
43 130 1
45 136 3
47 142 1
49 148 2
51 154 1
53 160 5
55 166 1
57 172 2
59 178 1
61 184 3
63 190 1
65 196 2
67 202 1
69 208 4
71 214 1
73 220 2
75 226 1
77 232 3
79 238 1
81 244 2
83 250 1
85 256 8
87 262 1
89 268 2
91 274 1
93 280 3
95 286 1
97 292 2
99 298 1