Сиракузская последовательность генерируется следующим образом. Берем любое натуральное число n. Если оно четное, то делим его на 2, а если нечетное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.
Немецкий математик Коллатц выдвинул гипотезу: какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.
Напишите функцию, которая будет принимать в качестве аргумента число и возвращать кортеж из двух элементов: количества шагов сиракузской последовательности для переданного числа и наибольшее число в этой последовательности.
Примечание: если найдете начальное положительное число, сиракузская последовательность для которого не закончится единицей, — впишете свое имя в историю математики и получите денежную премию.
Примеры
collatz(2) ➞ (2, 2) # seq = [2, 1] collatz(3) ➞ (8, 16) # seq = [3, 10, 5, 16, 8, 4, 2, 1] collatz(7) ➞ (17, 52) # seq = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] collatz(8) ➞ (4, 8) # seq = [8, 4, 2, 1]
Варианты решения
def collatz(n):
res = []
while n != 1:
res.append(n)
n = n * 3 + 1 if n % 2 else n // 2
return len(res) + 1, max(res)
def collatz(n):
s, m = 1, n
while n > 1:
if n % 2:
n = (n * 3) + 1
else:
n /= 2
s += 1
m = max(m, int(n))
return (s, m)