76 lines
1.8 KiB
Python
76 lines
1.8 KiB
Python
# The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors
|
|
# of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.
|
|
#
|
|
# Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220,
|
|
# forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.
|
|
#
|
|
# Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:
|
|
#
|
|
# 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → ...)
|
|
#
|
|
# Since this chain returns to its starting point, it is called an amicable chain.
|
|
#
|
|
# Find the smallest member of the longest amicable chain with no element exceeding one million.
|
|
|
|
from numpy import zeros
|
|
|
|
from projecteuler import sum_of_divisors, timing
|
|
|
|
|
|
N = 1000000
|
|
divisors = zeros(N + 1)
|
|
|
|
|
|
def sociable_chain(i, chain, l, min_):
|
|
chain[l] = i
|
|
|
|
if i == 1:
|
|
return -1
|
|
|
|
if divisors[i] != 0:
|
|
n = int(divisors[i])
|
|
else:
|
|
n = int(sum_of_divisors(i))
|
|
|
|
if n > N:
|
|
return -1
|
|
|
|
if n == chain[0]:
|
|
return l + 1
|
|
|
|
for j in range(l, 0, -1):
|
|
if n == chain[j]:
|
|
return -1
|
|
|
|
if n < min_:
|
|
min_ = n
|
|
|
|
return sociable_chain(n, chain, l + 1, min_)
|
|
|
|
|
|
@timing
|
|
def p095():
|
|
chain = zeros(N)
|
|
min_ = 0
|
|
l_max = 0
|
|
|
|
for i in range(4, N + 1):
|
|
divisors[i] = sum_of_divisors(i)
|
|
|
|
if divisors[i] == i:
|
|
continue
|
|
|
|
min_tmp = i
|
|
length = sociable_chain(i, chain, 0, min_tmp)
|
|
|
|
if length > l_max:
|
|
l_max = length
|
|
min_ = min_tmp
|
|
|
|
print('Project Euler, Problem 95')
|
|
print(f'Answer: {min_}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p095()
|