127 lines
3.3 KiB
Python
127 lines
3.3 KiB
Python
from functools import lru_cache
|
|
|
|
|
|
def euler_078():
|
|
piles_look_up = {}
|
|
|
|
def count_piles_limited(n, max_size):
|
|
if max_size == 1:
|
|
return 1
|
|
try:
|
|
return piles_look_up[(n, max_size)]
|
|
except KeyError:
|
|
pass
|
|
|
|
count = 0
|
|
for i in range(1, n):
|
|
n_new = n - i
|
|
count_i = count_piles_limited(n_new, min([n_new, i]))
|
|
count += count_i
|
|
piles_look_up[(n, i)] = count
|
|
# for n itself
|
|
count += 1
|
|
piles_look_up[(n, n)] = count
|
|
return count
|
|
|
|
piles_look_up_modular = {}
|
|
|
|
def count_piles_limited_modular(n, max_size, modulu):
|
|
if max_size == 1:
|
|
return 1
|
|
try:
|
|
return piles_look_up_modular[(n, max_size)]
|
|
except KeyError:
|
|
pass
|
|
|
|
count = 0
|
|
for i in range(1, n):
|
|
n_new = n - i
|
|
count_i = count_piles_limited_modular(
|
|
n_new, min([n_new, i]), modulu)
|
|
count = (count + count_i) % modulu
|
|
piles_look_up_modular[(n, i)] = count
|
|
# for n itself
|
|
count = (count + 1) % modulu
|
|
piles_look_up_modular[(n, n)] = count
|
|
return count
|
|
|
|
@lru_cache(maxsize=1000000)
|
|
def count_piles(n, max_size):
|
|
if max_size == 0 or max_size == 1:
|
|
return 1
|
|
if n == 0 or n == 1:
|
|
return 1
|
|
|
|
count = 0
|
|
for k in range(1, max_size + 1):
|
|
n_new = n - k
|
|
max_size_new = min([k, n_new])
|
|
count += count_piles(n_new, max_size_new)
|
|
return count
|
|
|
|
"""
|
|
I tried to implement my own algorithm but I would run out of memory.
|
|
I tried to find a pattern in how the count can be calculated directly,
|
|
but I could not find a pattern. I then looked up partioning and
|
|
implemented the algorithm explained here [1]. This was literally the first
|
|
time in my life that I have learned about generator functions. Once I
|
|
used this algorithm it was easy. I definitely want to learn more about
|
|
generator functions.
|
|
|
|
[1] https://www.coursera.org/lecture/enumerative-combinatorics/computing-the-number-of-partitions-via-the-pentagonal-theorem-CehOM
|
|
"""
|
|
|
|
def sign(n):
|
|
if n % 2 == 0:
|
|
return -1
|
|
return 1
|
|
|
|
@lru_cache(maxsize=1000000)
|
|
def euler_identity(n):
|
|
r = (3 * n * n - n) // 2
|
|
return r
|
|
|
|
@lru_cache(maxsize=1000000)
|
|
def p(n):
|
|
"""
|
|
"""
|
|
if n == 0:
|
|
return 1
|
|
if n == 1:
|
|
return 1
|
|
|
|
m = 1000000
|
|
r = 0
|
|
for i in range(1, n):
|
|
s = sign(i)
|
|
|
|
e = euler_identity(i)
|
|
new_n = n - e
|
|
if new_n < 0:
|
|
break
|
|
if m:
|
|
r = (r + s * p(new_n)) % m
|
|
else:
|
|
r = r + s * p(new_n)
|
|
|
|
e = euler_identity(-i)
|
|
new_n = n - e
|
|
if new_n < 0:
|
|
break
|
|
if m:
|
|
r = (r + s * p(new_n)) % m
|
|
else:
|
|
r = r + s * p(new_n)
|
|
return r
|
|
|
|
for n in range(1, 100000):
|
|
a = p(n)
|
|
if a == 0:
|
|
return n
|
|
break
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e078.py: " + str(euler_078()))
|
|
assert(euler_078() == 55374)
|