Python Implementation of Problem 123
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 123
Brute force, with minor optimizations, seems to have worked here. Using cython shaved a few seconds off the runtime, but not enough to be hugely noticable. Additionally, I narrowed the search range by figuring that the remainder has to take place after the prime is 10**5.
Revision 1:
Reduce search space further by remembering that it's unlikely for n % (10**10 + epsilon) >= 10**10
Problem:
Let p[n] be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (p[n]−1)**n + (p[n]+1)**n is divided by p[n]**2.
For example, when n = 3, p[3] = 5, and 4**3 + 6**3 = 280 ≡ 5 mod 25.
The least value of n for which the remainder first exceeds 10**9 is 7037.
Find the least value of n for which the remainder first exceeds 10**10.
1"""
2Project Euler Problem 123
3
4Brute force, with minor optimizations, seems to have worked here. Using cython
5shaved a few seconds off the runtime, but not enough to be hugely noticable.
6Additionally, I narrowed the search range by figuring that the remainder has to
7take place after the prime is 10**5.
8
9Revision 1:
10
11Reduce search space further by remembering that it's unlikely for n % (10**10 + epsilon) >= 10**10
12
13Problem:
14
15Let p[n] be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when
16(p[n]−1)**n + (p[n]+1)**n is divided by p[n]**2.
17
18For example, when n = 3, p[3] = 5, and 4**3 + 6**3 = 280 ≡ 5 mod 25.
19
20The least value of n for which the remainder first exceeds 10**9 is 7037.
21
22Find the least value of n for which the remainder first exceeds 10**10.
23"""
24from .lib.primes import primes
25
26
27def main() -> int:
28 min_p = 235_000
29 ten_ten = 10**10
30 for n, p in enumerate(primes(), 1):
31 if p < min_p or n & 1 == 0: # Seems to always produce remainder of 2?
32 continue
33 base = ((p-1)**n + (p+1)**n)
34 if base % (p * p) > ten_ten:
35 return n
36 return -1 # pragma: no cover