Project-Euler/Problem014_Longest_Collatz_sequence.py at master · moussatat/Project-Euler · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
# -*- coding: utf-8 -*-
# Problem 014 Longest Collatz sequence
#The following iterative sequence is defined for the set of positive integers:
#
#n → n/2 (n is even)
#n → 3n + 1 (n is odd)
#
#Using the rule above and starting with 13, we generate the following sequence:
#
#13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
#It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
#Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
#
#Which starting number, under one million, produces the longest chain?
#
#NOTE: Once the chain starts the terms are allowed to go above one million.
import time
start=time.time()
###########################
# Method 1
n=10**6

D = [ -1 for i in range(0,n+1)]
for i in range(1,n+1) :
    u = i
    D[i]=0
    compteur = 0
    while u > 1 :
        if u%2==0 :
            u = u//2
            compteur = compteur + 1
        else :
            u = (3 * u + 1)//2
            compteur = compteur + 2
            ## if n is odd, the next term is even, gain 1/2 a second
        if u <= n and D[u] != -1 :
            break
    D[i] = D[u] + compteur

maximum = max(D)
rang=D.index(max(D))
print(rang, maximum)
##########################
#temps pour trouver la réponse :
end=time.time()
print(f"temps pour trouver la réponse : {end-start}")
start=time.time()
##########################
# Method 2
#n=10**6
D = [ -1 for i in range(0,n+1)]
D[1]=0
j = 1
while j <=  n :
    i = j
    while D[i] != -1 and i<n :
        i = i + 1
    j = i + 1
    L = [i]
    u = i
    compteur = 0
    while u > 1 :
        if u%2==0 :
            u = u//2
            compteur = compteur + 1
        else :
            u = (3 * u + 1)//1
            compteur = compteur + 1
        if  u <= n and D[u] != -1 :
            break
        L.append(u)
    for k in range(len(L)) :
        if L[k] <= n :
            D[L[k]] = D[u] + compteur - k
#    j = j + 1

maximum = max(D)
rang=D.index(max(D))
print(rang, maximum)
##########################
#temps pour trouver la réponse :
end=time.time()
print(f"temps pour trouver la réponse : {end-start}")
start=time.time()
##########################
# Given answer on site
def collatz(n) :
    if n == 1 :
        return 0
    elif n%2==0 :
        return 1 + collatz(n//2)
    else :
        return 2 + collatz((3*n+1)//2)

reponse=0
maximum= -1
for i in range(n//2, n+1) :
    longueur=collatz(i)
    if maximum < longueur:
        reponse=i
        maximum = longueur
print(reponse, maximum)
##########################
#temps pour trouver la réponse :
end=time.time()
print(f"temps pour trouver la réponse : {end-start}")