#!/usr/bin/env python3
"""Module-level comment."""

# il faut écrire collatz ...

def nb_etapes(n):
	nb_etapes = 0
	while n != 1 :
		if n % 2 == 0 :
			n = n/2  
		else :
			n = 3*n + 1
		nb_etapes += 1
	return nb_etapes

def collatz(m):
	max = 1
	for i in range(2,m):
		if nb_etapes(i) > max:
			max = nb_etapes(i)
	return max

def collatz_len_fast(n, cache):
		"""Calculer plus rapidement la séquence collatz.
		L'idee est de sauvegarder les longueurs des chiffres déjà calculés
		Pour cela, on va utiliser un dictionnaire 
		"""
		if n == 1:
				return 1
		if n in cache:
				return cache[n]

		if n % 2 == 0:
				cache[n] = collatz_len_fast(n // 2, cache) + 1
		else:
				cache[n] = collatz_len_fast(3 * n + 1, cache) + 1
		return cache[n]


def max_collatz_len_fast(n):
	cache = {}
	res = 1
	for i in range(n // 2, n):
		collatz_len_fast(i, cache)

	for i in range(n // 2, n):
		if res < cache[i]:
			res = cache[i]
	return res
			
	#return max(collatz_len_fast(i, cache) for i in range(n // 2, n))


def main():
	m = 10000000
	#print("Le nb_etapes maximal de 1 à ", m, " est", collatz(m))
	print("Le nb_etapes maximal de 1 à ", m, " est", max_collatz_len_fast(m))
	return 0

if __name__ == '__main__':
    main()