sol1.py

"""
Project Euler Problem 77: https://projecteuler.net/problem=77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over
five thousand different ways?
"""

from __future__ importannotations

fromfunctoolsimportlru_cache
frommathimportceil

NUM_PRIMES=100

primes=set(range(3, NUM_PRIMES, 2))
primes.add(2)
prime: int

forprimeinrange(3, ceil(NUM_PRIMES**0.5), 2):
ifprimenotinprimes:
continue
primes.difference_update(set(range(prime*prime, NUM_PRIMES, prime)))


@lru_cache(maxsize=100)
defpartition(number_to_partition: int) ->set[int]:
"""
 Return a set of integers corresponding to unique prime partitions of n.
 The unique prime partitions can be represented as unique prime decompositions,
 e.g. (7+3) <-> 7*3 = 12, (3+3+2+2) = 3*3*2*2 = 36
 >>> partition(10)
 {32, 36, 21, 25, 30}
 >>> partition(15)
 {192, 160, 105, 44, 112, 243, 180, 150, 216, 26, 125, 126}
 >>> len(partition(20))
 26
 """
ifnumber_to_partition<0:
returnset()
elifnumber_to_partition==0:
return {1}

ret: set[int] =set()
prime: int
sub: int

forprimeinprimes:
ifprime>number_to_partition:
continue
forsubinpartition(number_to_partition-prime):
ret.add(sub*prime)

returnret


defsolution(number_unique_partitions: int=5000) ->int|None:
"""
 Return the smallest integer that can be written as the sum of primes in over
 m unique ways.
 >>> solution(4)
 10
 >>> solution(500)
 45
 >>> solution(1000)
 53
 """
fornumber_to_partitioninrange(1, NUM_PRIMES):
iflen(partition(number_to_partition)) >number_unique_partitions:
returnnumber_to_partition
returnNone


if__name__=="__main__":
print(f"{solution() =}")