from time import time

N = 1_000_000
seq_lens = [0] * N # make an array of 0's of size N
seq_lens[1] = 1

start_time = time()

max_n = 1
for n in range(2, N):
    l = 0
    x = n
    while x >= N or seq_lens[x] == 0: # either we're outside the range of the array or we're at unvisited numbers
        if x % 2 == 0:
            x = x // 2
        else:
            x = 3 * x + 1
        l += 1

    # "distance" n to 1 is the "distance" of n to x plus the "distance" of x to 1.
    seq_lens[n] = seq_lens[x] + l

    if seq_lens[n] > seq_lens[max_n]:
        max_n = n

end_time = time()

print(max_n)
print("took", end_time - start_time, "seconds")