Python Implementation of Problem 77
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 77
I was able to recycle a lot of the work on #76 for this, though I did have to undo some optimizations to get there
Problem:
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?
1"""
2Project Euler Problem 77
3
4I was able to recycle a lot of the work on #76 for this, though I did have to undo some optimizations to get there
5
6Problem:
7
8It is possible to write ten as the sum of primes in exactly five different ways:
9
107 + 3
115 + 5
125 + 3 + 2
133 + 3 + 2 + 2
142 + 2 + 2 + 2 + 2
15
16What is the first value which can be written as the sum of primes in over five thousand different ways?
17"""
18from itertools import count
19from typing import List, Tuple
20
21from .lib.primes import primes
22
23
24def prime_summations(n: int) -> int:
25 answer = 0
26 cached_primes: Tuple[int, ...] = tuple(primes(n))
27 num_primes = len(cached_primes)
28 max_idx = num_primes - 1
29 counts: List[int] = [0] * num_primes
30 # counts is a list containing how many times you add each prime
31 # so for 5 + 5 + 3 + 2 it would be [1, 1, 2]
32 counts[0] = n // 2 # primes[0] = 2
33 while True:
34 total = sum(x * y for x, y in zip(counts, cached_primes))
35 counts[0] += 1
36 if total > n:
37 idx = 0
38 while total > n and idx < max_idx:
39 counts[idx] = 0
40 idx += 1
41 counts[idx] += 1
42 total = sum(x * y for x, y in zip(counts, cached_primes))
43 if idx >= max_idx:
44 break
45 counts[0] = (n - total) // 2 # primes[0] = 2
46 elif total == n:
47 answer += 1
48 return answer
49
50
51def main() -> int:
52 for x in count(11):
53 if prime_summations(x) > 5_000:
54 return x
55 return -1 # pragma: no cover