78 lines
1.8 KiB
Python
78 lines
1.8 KiB
Python
"""
|
|
The following iterative sequence is defined for the set of positive integers:
|
|
|
|
n -> n/2 (is even)
|
|
n -> 3n + 1 (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?
|
|
"""
|
|
|
|
import time
|
|
from functools import cache
|
|
|
|
|
|
def timer(func):
|
|
def wrapper(*args, **kwargs):
|
|
start_time = time.time()
|
|
result = func(*args, **kwargs)
|
|
end_time = time.time()
|
|
print(f"{func.__name__} took {end_time - start_time:.6f} seconds")
|
|
return result
|
|
|
|
return wrapper
|
|
|
|
|
|
def is_even(n: int) -> bool:
|
|
return n & 1 == 0
|
|
|
|
|
|
def collatz_sequence(n: int) -> list[int]:
|
|
sequence = [n]
|
|
while sequence[-1] != 1:
|
|
if is_even(n):
|
|
n = n // 2
|
|
else:
|
|
n = 3 * n + 1
|
|
sequence.append(n)
|
|
return sequence
|
|
|
|
|
|
def longest_collatz_sequence(limit: int) -> int:
|
|
longest_length = 0
|
|
longest_start = 0
|
|
for i in range(1, limit + 1):
|
|
length = len(collatz_sequence(i))
|
|
if length > longest_length:
|
|
longest_length = length
|
|
longest_start = i
|
|
return longest_start
|
|
|
|
|
|
@cache
|
|
def chain_length(n):
|
|
if n == 1:
|
|
return 0
|
|
next_term = 3 * n + 1 if n % 2 else n // 2
|
|
return chain_length(next_term) + 1
|
|
|
|
|
|
@timer
|
|
def main_do() -> None:
|
|
print(longest_collatz_sequence(1000000))
|
|
|
|
|
|
@timer
|
|
def main_cache() -> None:
|
|
print(max(range(1, 1000001), key=chain_length))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main_do()
|
|
main_cache()
|