71 lines
1.4 KiB
Python
71 lines
1.4 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# Two solutions, recursive order of magniture faster
|
|
|
|
def base(k):
|
|
lim = 2*k
|
|
cache = [False for i in range(k+1)]
|
|
for n in range(2, lim+1):
|
|
recursive(n, n, n, lim, 2, cache)
|
|
return sum(set(cache[2:]))
|
|
|
|
def recursive(s, p, n, lim, d, cache): #sum, product, last digit, limit, depth
|
|
m = p*n #number
|
|
x = n
|
|
while m <= lim:
|
|
ns = s+x
|
|
k = m - ns + d
|
|
if k <= lim//2 and (not cache[k] or cache[k] > m):
|
|
cache[k] = m
|
|
recursive(ns, m, x, lim, d+1, cache)
|
|
x += 1
|
|
m += p
|
|
|
|
|
|
|
|
def main(k):
|
|
return sum(set([minnum(i) for i in range(2, k+1)]))
|
|
|
|
def minnum(k):
|
|
s = [2, 2]
|
|
s[0], mod = findn(k, s)
|
|
r = num(k, s)
|
|
while set(s[1:]) != {2} or s[0] > 2:
|
|
count(s)
|
|
s[0], mod = findn(k, s)
|
|
if mod == 0 and s[0] >= s[1] and num(k, s) < r:
|
|
r = num(k, s)
|
|
return r
|
|
|
|
def count(s):
|
|
i = 0
|
|
while i < len(s)-2 and s[i] <= s[i+1]:
|
|
s[i+2] += 1
|
|
i += 1
|
|
if s[i] <= s[i+1]:
|
|
s.append(2)
|
|
i += 1
|
|
if i == 0:
|
|
s[1] += 1
|
|
else:
|
|
for j in range(i+1):
|
|
s[j] = s[i+1]
|
|
|
|
def num(k, s):
|
|
return k-len(s) + sum(s)
|
|
|
|
def findn(k, s):
|
|
a = k-len(s) + sum(s[1:])
|
|
b = pro(s[1:]) - 1
|
|
return a//b, a%b
|
|
|
|
def pro(s):
|
|
r = 1
|
|
for i in s:
|
|
r *= i
|
|
return r
|
|
|
|
#print(base(6))
|
|
#print(base(12))
|
|
print(base(12000))
|