Python Implementation of Problem 123
View source code here on GitHub!
Includes
Problem Solution
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