76 lines
1.9 KiB
Python
76 lines
1.9 KiB
Python
from lib_misc import get_item_counts
|
|
from lib_prime import primes
|
|
|
|
|
|
def divisors(counts):
|
|
r = 1
|
|
for c in counts:
|
|
r *= (c + 1)
|
|
return r
|
|
|
|
|
|
def tau(factors):
|
|
orig_factors = factors
|
|
factors = factors + factors
|
|
counts = get_item_counts(factors)
|
|
r = divisors(counts.values())
|
|
p = 1
|
|
for f in orig_factors:
|
|
p *= f
|
|
return r, p
|
|
|
|
|
|
def counters(digits, max_digit):
|
|
def incrementing_counters(curr, left, max_digit, result):
|
|
if left == 0:
|
|
result.append(curr)
|
|
return
|
|
start = 1 if not curr else curr[-1]
|
|
for i in range(start, max_digit + 1):
|
|
incrementing_counters(curr + [i], left - 1, max_digit, result)
|
|
|
|
result = []
|
|
incrementing_counters([], digits, max_digit, result)
|
|
return result
|
|
|
|
|
|
def euler_110():
|
|
target = 1000
|
|
target = 4 * 10**6
|
|
threshold = (target * 2) - 1
|
|
psupper = primes(1000)
|
|
|
|
lowest_distinct = 0
|
|
lowest_number = 0
|
|
|
|
# find upper bound
|
|
for i in range(len(psupper)):
|
|
distinct, number = tau(psupper[:i])
|
|
if distinct > threshold:
|
|
# print(lowest_distinct, number)
|
|
lowest_distinct = distinct
|
|
lowest_number = number
|
|
psupper = psupper[:i]
|
|
|
|
for j in range(1, len(psupper)):
|
|
ps = psupper[:-j]
|
|
for prime_counts in counters(len(ps), 5):
|
|
prime_counts.reverse()
|
|
nps = []
|
|
i = 0
|
|
for i in range(len(prime_counts)):
|
|
nps += [ps[i]] * prime_counts[i]
|
|
nps += ps[i + 1:]
|
|
distinct, number = tau(nps)
|
|
if distinct > threshold and distinct < lowest_distinct:
|
|
lowest_distinct = distinct
|
|
lowest_number = number
|
|
# print(lowest_distinct, lowest_number)
|
|
return lowest_number
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_110()
|
|
print("e110.py: " + str(solution))
|
|
assert(solution == 9350130049860600)
|