Задача 14.Самая длинная последовательность Коллатца

Условие:

Следующая повторяющаяся последовательность определена для множества натуральных чисел:

n → n/2 (n - чётное)
n → 3n + 1 (n - нечётное)

Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов. Хотя это до сих пор и не доказано (проблема Коллатца (Collatz)), предполагается, что все сгенерированные таким образом последовательности оканчиваются 1.
Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?

Решение

Гипотеза Коллатца сводится к тому что данная последовательность всегда оканчивается единицей. Если верить Википедии, то она не доказана и над проверкой гипотезы на больших числах сейчас трудятся миллионы видеокарт добровольцев вычислительной сети BOINC в рамках проекта Collatz Conjecture.

Мы же будем работать с не очень большими числами и банальной рекурсии нам с головой хватит. 

Функция get_collatz рекурсивно перебирает последовательность и возвращает количество итераций когда последовательность вышла на 1 

def get_collatz(n,qty):
    if n==1:
        return qty
    elif n%2==0:
        return get_collatz(int(n/2),qty+1)
    else:
        return get_collatz(3*n+1,qty+1)
n=0
a=0
for i in range(13,1000000):
    c=get_collatz(i,1)
    if c>n:
        a,n=i,c
print(a,n)

Далее в цикле перебираем числа начиная с 13-ти. Если число итераций > предыдущего записываем в переменную a само число, а в n длину его последовательности.
Вся эта конструкция работала около 2-х минут на моем скромном ноутбуке.