68 lines
1.7 KiB
Python
68 lines
1.7 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# The following iterative sequence is defined for the set of positive integers:
|
|
#
|
|
# n → n/2 (n is even)
|
|
# n → 3n + 1 (n 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?
|
|
#
|
|
# NOTE: Once the chain starts the terms are allowed to go above one million.
|
|
|
|
from numpy import zeros
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
N = 1000000
|
|
collatz_found = zeros(N, dtype=int)
|
|
|
|
|
|
# Recursive function to calculate the Collatz sequence for n.
|
|
# If n is even, Collatz(n)=1+Collatz(n/2), if n is odd
|
|
# Collatz(n)=1+Collatz(3*n+1).
|
|
def collatz_length(n: int) -> int:
|
|
|
|
if n == 1:
|
|
return 1
|
|
|
|
# If Collatz(n) has been previously calculated,
|
|
# just return the value.
|
|
if n < N and collatz_found[n]:
|
|
return collatz_found[n]
|
|
|
|
if n % 2 == 0:
|
|
return 1 + collatz_length(n//2)
|
|
|
|
return 1 + collatz_length(3*n+1)
|
|
|
|
|
|
@timing
|
|
def p014() -> None:
|
|
max_l = 0
|
|
_max = 0
|
|
|
|
# For each number from 1 to 1000000, find the length of the sequence
|
|
# and save its value, so that it can be used for the next numbers.
|
|
for i in range(1, N):
|
|
count = collatz_length(i)
|
|
collatz_found[i] = count
|
|
|
|
if count > max_l:
|
|
max_l = count
|
|
_max = i
|
|
|
|
print('Project Euler, Problem 14')
|
|
print(f'Answer: {_max}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p014()
|