Python Implementation of Problem 145
View source code here on GitHub!
Includes
Problem Solution
1"""
2Project Euler Problem 145
3
4For some reason there are no solutions above 10**8, so you can reduce the search space by a lot. In addition, you never
5need to check numbers divisble by 10, reducing it further. I think I've narrowed the valid search space to ~4.5% of the
6one given by the problem.
7
8Revision 1:
9
10Turns out that using the built-in repr function makes this go much (~5x) faster, so I'll switch to that until I find a
11narrower solution. It's very nearly at the 60s mark now.
12
13Revision 2:
14
15I reduced the search space by trial and error, getting it down to ~3.15% of the original
16
17Problem:
18
19Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits.
20For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are
21reversible. Leading zeroes are not allowed in either n or reverse(n).
22
23There are 120 reversible numbers below one-thousand.
24
25How many reversible numbers are there below one-billion (10^9)?
26"""
27from itertools import chain
28from typing import Set
29
30
31def main() -> int:
32 seen: Set[int] = set()
33 seen_update = seen.update
34 odd_digits = {"1", "3", "5", "7", "9"}
35 for x in chain.from_iterable(range(x, 10**8 // 2, 10) for x in (2, 4, 5, 6, 7, 8)):
36 if x in seen:
37 continue
38 inverse = int(repr(x)[::-1])
39 if all(digit in odd_digits for digit in repr(x + inverse)):
40 seen_update((x, inverse))
41 return len(seen)