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, 10
(number_to_partition: int)
| 32 | |
| 33 | @lru_cache(maxsize=100) |
| 34 | def partition(number_to_partition: int) -> set[int]: |
| 35 | """ |
| 36 | Return a set of integers corresponding to unique prime partitions of n. |
| 37 | The unique prime partitions can be represented as unique prime decompositions, |
| 38 | e.g. (7+3) <-> 7*3 = 12, (3+3+2+2) = 3*3*2*2 = 36 |
| 39 | >>> partition(10) |
| 40 | {32, 36, 21, 25, 30} |
| 41 | >>> partition(15) |
| 42 | {192, 160, 105, 44, 112, 243, 180, 150, 216, 26, 125, 126} |
| 43 | >>> len(partition(20)) |
| 44 | 26 |
| 45 | """ |
| 46 | if number_to_partition < 0: |
| 47 | return set() |
| 48 | elif number_to_partition == 0: |
| 49 | return {1} |
| 50 | |
| 51 | ret: set[int] = set() |
| 52 | prime: int |
| 53 | sub: int |
| 54 | |
| 55 | for prime in primes: |
| 56 | if prime > number_to_partition: |
| 57 | continue |
| 58 | for sub in partition(number_to_partition - prime): |
| 59 | ret.add(sub * prime) |
| 60 | |
| 61 | return ret |
| 62 | |
| 63 | |
| 64 | def solution(number_unique_partitions: int = 5000) -> int | None: |