Python Implementation of Problem 134
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 134
Officially I have this solved, but it took 76 core-minutes, which is just not a reasonable runtime. I have made some minor optimizations in the hopes that it will be reduced further, but it only went down to 37 core-minutes. Not good enough.
Revision 1:
Found Chinese Remainder Theorem, applied it, got infinity x speed boost
Problem:
Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.
In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.
Find ∑ S for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.
1"""
2Project Euler Problem 134
3
4Officially I have this solved, but it took 76 core-minutes, which is just not a
5reasonable runtime. I have made some minor optimizations in the hopes that it
6will be reduced further, but it only went down to 37 core-minutes. Not good
7enough.
8
9Revision 1:
10
11Found Chinese Remainder Theorem, applied it, got infinity x speed boost
12
13Problem:
14
15Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that
161219 is the smallest number such that the last digits are formed by p1 whilst
17also being divisible by p2.
18
19In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive
20primes, p2 > p1, there exist values of n for which the last digits are formed
21by p1 and n is divisible by p2. Let S be the smallest of these values of n.
22
23Find ∑ S for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.
24"""
25from .lib.math import mul_inv
26from .lib.primes import primes
27
28
29def main() -> int:
30 answer: int = 0
31 pow_10: int = 10
32 iterator = primes(1000005) # iterate over primes <1000005
33 next(iterator) # skip 2
34 next(iterator) # skip 3
35 p1: int = next(iterator) # p1 = 5
36 for p2 in iterator: # 7, 11, 13, 17, ...
37 while pow_10 < p1:
38 pow_10 *= 10
39 answer += (p1 * p2 * mul_inv(p2, pow_10)) % (p2 * pow_10)
40 # simplified Chinese Remainder Theorem
41 p1 = p2
42 return answer