Python Implementation of Problem 145

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 145

For some reason there are no solutions above 10**8, so you can reduce the search space by a lot. In addition, you never need to check numbers divisble by 10, reducing it further. I think I've narrowed the valid search space to ~4.5% of the one given by the problem.

Revision 1:

Turns out that using the built-in repr function makes this go much (~5x) faster, so I'll switch to that until I find a narrower solution. It's very nearly at the 60s mark now.

Revision 2:

I reduced the search space by trial and error, getting it down to ~3.15% of the original

Problem:

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10^9)?

python.src.p0145.main() → int
 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)

Tags: digit-manipulation, combinatorics