Problem 145: How Many Reversible Numbers Are There Below One-Billion?

Project Euler Problem 145 Solution

EulerSolve provides an optimized solution for Project Euler Problem 145, How Many Reversible Numbers Are There Below One-Billion?, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A positive integer $n$ is called reversible when $n+\operatorname{rev}(n)$ is made entirely of odd digits, and neither $n$ nor its reversal is allowed to acquire leading zeros. For numbers below $10^9$, that means counting all valid lengths from 1 through 9 while excluding any number ending in 0. The important point is that reversibility is controlled by base-10 addition with carries. Once the digits are grouped into mirrored pairs, the search stops being about individual integers and becomes a finite combinatorial count over pair sums and carry states. Mathematical Approach Write an $L$-digit number as $$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$ The condition $x_0\neq 0$ is exactly the rule that the reversal may not begin with 0. The whole argument comes from studying the addition $n+\operatorname{rev}(n)$ column by column. Mirrored columns and the carry recurrence Column $i$ adds the mirrored digits $x_i$ and $x_{L-1-i}$. With incoming carry $c_i$ and $c_0=0$, define $$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$ Reversibility means every visible digit $d_i$ is odd. Because $x_i+x_{L-1-i}\le 18$, every carry is either 0 or 1....

Detailed mathematical approach

Problem Summary

For a positive integer $n$, let $\operatorname{rev}(n)$ be the number with the decimal digits of $n$ in reverse order. The number $n$ is called reversible if every decimal digit of $n+\operatorname{rev}(n)$ is odd, as in $36+63=99$ and $409+904=1313$. Leading zeros are not allowed in $n$ or in $\operatorname{rev}(n)$, which excludes exactly the numbers that end in $0$. There are $120$ reversible numbers below one thousand, and we must count those below one billion, $10^9$. ^[1]

The whole solution in one sentence: the two digits at equal distance from the ends of $n$ are added twice, in two mirror-image columns of the sum, and since both columns must show odd digits they receive the same carry, which forces all carries into a fixed alternating pattern and turns the count for each length into a product of the numbers of allowed digit pairs.

Mathematical Approach

1. One, two and three digits

A one-digit number $d$ gives $d+d=2d$, whose last digit is even, so it is never reversible.

A two-digit number $n=10a+b$ needs $b\ge1$, since its reverse may not begin with $0$, and gives $n+\operatorname{rev}(n)=11(a+b)$. If $s=a+b\le9$, both digits of the sum equal $s$, as in $36+63=99$. If $s\ge10$, the sum has the tens digit $s-9$ and the units digit $s-10$, as in $47+74=121$, and one of these consecutive numbers is even. So the reversible two-digit numbers are those with $a+b\in\{3,5,7,9\}$. Such a sum $s$ arises from $s-1$ ordered pairs of nonzero digits, which gives $2+4+6+8=20$ numbers, from $12$ to $81$. The rule about leading zeros matters here: a program that turned the reverse of $10$ into $1$ would accept $10$, $30$, $50$, $70$ and $90$, because $10+1=11$, and would count $125$ numbers below one thousand.

A three-digit number $n=100a+10b+c$ with $a,c\ge1$ has the column sums $a+c$, $2b$ and $a+c$, from right to left. The middle column $2b$ is even, so it needs a carry from the units column, which means $a+c\ge10$, and the units digit $a+c-10$ must be odd: $a+c\in\{11,13,15,17\}$. The middle column then holds $2b+1$ and must not carry, or the left column would hold the even number $a+c+1$ and show an even digit; so $b\le4$. For instance, $409+904=1313$ has $a+c=13$ and $b=0$. The four sums come from $8+6+4+2=20$ ordered pairs $(a,c)$, so there are $20\cdot5=100$ three-digit reversible numbers. With the two-digit ones these are the $120$ numbers of the statement, the first terms of the OEIS sequence A135739. ^[2]

2. Mirror columns

Write a number with $L$ digits as $n=\sum_{i=0}^{L-1}a_i10^i$, with $a_{L-1}\ne0$ and, by the rule on leading zeros, $a_0\ne0$. The reverse has the digit $a_{L-1-i}$ in place $i$, so

$$\begin{aligned}n+\operatorname{rev}(n)&=\sum_{i=0}^{L-1}s_i\,10^i,\\s_i&=a_i+a_{L-1-i}.\end{aligned}$$

The column sums are symmetric, $s_i=s_{L-1-i}$: the two digits added in column $i$ are added again in the mirror column $L-1-i$. For odd $L$ the middle column $k=(L-1)/2$ has $s_k=2a_k$. Whether $n$ is reversible therefore depends only on the $h=\lfloor L/2\rfloor$ pair sums $s_0,\dots,s_{h-1}$ and, for odd $L$, on the middle digit.

3. Carries and parity

The sum is formed column by column from the right. ^[3] Let $c_i$ be the carry into column $i$, with $c_0=0$. Column $i$ holds $t_i=s_i+c_i$, shows the digit $t_i$ or $t_i-10$, and passes on $c_{i+1}=1$ exactly when $t_i\ge10$. Since $t_i\le18+1$, every carry is $0$ or $1$, and a final carry $c_L=1$ only adds a leading digit $1$, which is odd. Subtracting $10$ does not change parity, ^[4] so column $i$ shows an odd digit exactly when $s_i+c_i$ is odd.

4. Mirror columns receive the same carry

Claim. If $n$ is reversible, then $c_i=c_{L-1-i}$ for every column $i$, and $c_{i+1}=c_{i-1}$ for $1\le i\le L-1$.

Proof. Columns $i$ and $L-1-i$ have the same sum $s_i$, and by Section 3 both $s_i+c_i$ and $s_i+c_{L-1-i}$ are odd. So $c_i$ and $c_{L-1-i}$ have the same parity, and as both are $0$ or $1$, they are equal. The two columns then hold the same total and pass on the same carry: $c_{i+1}=c_{L-i}$. For $1\le i\le L-1$, the first statement applied to column $L-i$ gives $c_{L-i}=c_{i-1}$, hence $c_{i+1}=c_{i-1}$. $\square$

Starting from $c_0=0$, every carry with an even index is $0$, and all carries with an odd index, up to $c_L$, share one value $e$. In $409+904$ the carries into the columns are $0,1,0$ and the last column passes on $1$, so $e=1$.

5. Counting digit pairs

Let $P(s)$ be the number of ordered pairs of digits from $1$ to $9$ with sum $s$, the choices for the outer pair $(a_0,a_{L-1})$, and $Q(s)$ the same count for digits from $0$ to $9$, the choices for an inner pair. Fixing the first digit $x$ of a pair fixes the second as $s-x$, so $P(s)$ counts the integers $x$ with $\max(1,s-9)\le x\le\min(9,s-1)$ and $Q(s)$ those with $\max(0,s-9)\le x\le\min(9,s)$:

$$\begin{aligned}P(s)&=\min(s-1,\,19-s),\\Q(s)&=\min(s+1,\,19-s)\end{aligned}$$

for $2\le s\le18$ and $0\le s\le18$ respectively, and $0$ otherwise; for example $P(9)=8$ and $Q(9)=10$. By the rule of product, ^[5] exactly $P(s_0)\,Q(s_1)\cdots Q(s_{h-1})$ numbers have given pair sums $s_0,\dots,s_{h-1}$ (and a given middle digit, for odd $L$), and by Section 2 either all of them are reversible or none is. Every number has exactly one pattern, so adding these products over the patterns of pair sums that give odd digits counts each reversible number once. For example, the four-digit numbers with $s_0=s_1=5$ are $P(5)\,Q(5)=4\cdot6=24$ numbers, among them $1234$ and $2143$, all giving $5555$, and this one pattern contributes all $24$ at once. The programs add the products pattern by pattern; Sections 6 and 7 evaluate the sum in closed form.

6. Even lengths

Let $L=2k$. Section 4 with $i=0$ gives $c_{L-1}=c_0=0$, and $L-1$ is odd, so $e=0$: a reversible number of even length produces no carry at all. By Section 3 every pair sum is then odd, and at most $9$, since a larger sum would carry. Conversely, if all pair sums are odd and at most $9$, no column carries and every column shows its odd sum. The outer pair has $P(3)+P(5)+P(7)+P(9)=20$ choices and each of the $k-1$ inner pairs has $Q(1)+Q(3)+\dots+Q(9)=30$, so the number of reversible numbers with $2k$ digits is

$$R_{2k}=20\cdot30^{k-1}.$$

This gives $R_2=20$, as in Section 1, and $R_4=600$.

7. Odd lengths

Let $L=2k+1$. The middle column has the even sum $s_k=2a_k$, so by Section 3 it needs $c_k=1$, and since carries with an even index are $0$, $k$ must be odd. For $L=4m+1$ the index $k=2m$ is even, so no reversible number has $1$, $5$, $9$, $13$, … digits. For $L=4m+3$ we have $k=2m+1$ and $e=1$: column $i$ receives the carry $0$ if $i$ is even and $1$ if $i$ is odd, and must pass on the other value. By Section 3 this means, for a pair index $i\lt k$ and for the middle column:

even $i$: $s_i$ is odd and at least $10$, so $s_i\in\{11,13,15,17\}$;
odd $i$: $s_i$ is even and $s_i+1\le9$, so $s_i\in\{0,2,4,6,8\}$;
the middle column, whose index $k$ is odd: $2a_k+1\le9$, so $a_k\le4$.

A column and its mirror have indices of the same parity, because $L-1=4m+2$ is even, so they impose the same condition on their common pair sum. Conversely, pair sums and a middle digit with these properties reproduce the pattern column by column from the right, and every column shows an odd digit. The outer pair has $P(11)+P(13)+P(15)+P(17)=20$ choices, and so has each of the $m$ inner pairs with an even index, since these sums use no digit $0$; each of the $m$ pairs with an odd index has $Q(0)+Q(2)+\dots+Q(8)=25$ choices, and the middle digit has $5$ choices, $0$ to $4$. Hence

$$\begin{aligned}R_{4m+3}&=20\cdot(20\cdot25)^m\cdot5\\&=100\cdot500^m,\\R_{4m+1}&=0.\end{aligned}$$

For $m=0$ this is the count $100$ of Section 1, and $R_7=50000$. For example, $2030809+9080302=11111111$ has the pair sums $11,0,11$, the middle digit $0$ and the carries $0,1,0,1,0,1,0,1$.

How the Code Works

All three programs add the counts of the lengths up to nine. In the C++ program, ^[7] parse_arguments accepts --skip-checkpoints and --limit= with a decimal limit, by default $10^9$; other arguments and the limit $0$ give exit code $1$. The digits are not checked for overflow: a value beyond $2^{64}-1$ silently wraps around modulo $2^{64}$, so that $2^{64}+1000$ acts as the limit $1000$.

count_for_length(length) counts the reversible numbers with exactly length digits, $0$ for one digit. It tabulates $P(s)$ and $Q(s)$ in outer_count and inner_count. The recursive lambda dfs, which receives itself as the parameter self, is a depth-first search ^[6] over the patterns of Section 5: at depth idx it tries every sum with a nonzero count, stores it in sums[idx] and multiplies the weight by $P(s)$ or $Q(s)$. At depth half, that is $h$, it calls apply_sequence once, or for an odd length once per middle digit $m=0,\dots,9$ with center_twice $=2m$. apply_sequence is the addition of Section 3: column $i$ takes its pair sum from sums[i] or, past the middle, from sums[length - 1 - i]; it returns $0$ at the first even digit and the weight otherwise, and its final test carry > 1 can never succeed. The search does not use Sections 4, 6 and 7; it simply tests every pattern.

solve(limit) adds count_for_length for every length below the digit count of limit - 1, and for that length too if limit is a power of ten, as $10^9$ is. Other limits up to $10^7$ are finished by testing the numbers of the last length one by one, skipping multiples of $10$; larger ones make solve throw an exception, which gives exit code $3$. Before that, unless switched off, run_checkpoints requires the counts $20$, $100$ and $50000$ for the lengths $2$, $3$ and $7$, with exit code $2$ on a failure. The helper is_power_of_ten is never called.

The Python and Java programs have no options or checkpoints and run the same search for the lengths $2$ to $9$. Python defines dfs and check, its version of apply_sequence, inside the loop over the lengths, passes the sums as a new list sums + [s] and adds the weights to total through nonlocal; Java overwrites one array of length $h$ and adds to a static long. In the default run the counts stay below $10^9$ and the weights at most $9000$, far from any overflow.

Complexity and Verification

For a length $L$ the search reaches $17\cdot19^{h-1}$ patterns, since $17$ sums are possible for the outer pair and $19$ for an inner one, with ten tests per pattern for odd $L$; a test stops at the first even digit, on average after fewer than two columns. For the lengths $2$ to $9$ these are $1353880$ tests with $2617136$ column steps, $1166030$ of the tests for $L=9$, where none can succeed. Besides two tables of $19$ counts, the memory is a recursion of at most $h+1$ levels with its pair sums; Python creates a new list at each level, at most $h(h+1)/2$ entries at once. For a limit $N=10^D$ the number of tests grows like $19^{D/2}\approx N^{0.64}$, and each test, like each list copy in Python, costs $O(D)$, so the time is $O(D\cdot19^{D/2})$; a direct test needs $O(D)$ digit operations for each of the $N$ numbers, the closed forms a few multiplications per length. On a desktop computer a whole run, start-up included, takes a few milliseconds in C++, a few hundredths of a second in Java and about a third of a second in Python.

Besides the C++ checkpoints, all three programs were run for this article and print the same number. A separate C program tested every number below $10^9$ directly, adding it to its reverse both as an integer and column by column: the two ways agree on every number, the count of every length $L\le9$ is $R_L$ of Sections 6 and 7, every reversible number has the carries of Sections 4, 6 and 7, and the total agrees with the programs. With --limit=1000 the C++ program prints $120$, and with --limit=1234, testing $1000$ to $1233$ one by one, the direct count $165$. These checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The carry pattern of Section 4 and the counts $R_L$ are derived in this article.

Project Euler 145 — Reversible Numbers. The official statement calls n reversible if n + reverse(n) consists entirely of odd decimal digits, gives 36 + 63 = 99 and 409 + 904 = 1313, allows no leading zeros, states that 120 reversible numbers lie below one thousand, and asks for the count below one billion.
OEIS A135739. Numbers k, not multiples of 10, such that k + reverse(k) has only odd decimal digits: 12, 14, 16, 18, 21, …, 72, 81, 209, 219, …
Wikipedia — Carry (arithmetic). A carry is a digit transferred from one column to a more significant one; in 27 + 59 = 86, the 1 of 7 + 9 = 16 is carried into the tens column.
Wikipedia — Parity (mathematics). Even ± even is even, even ± odd is odd and odd ± odd is even, and a decimal integer has the parity of its last digit.
Wikipedia — Rule of product. If there are a ways of doing one thing and b ways of doing another, there are a · b ways of doing both.
Wikipedia — Depth-first search. The search explores as far as possible along each branch before backtracking, and the article gives a recursive implementation.
C++ — Euler145.cpp. The linked immutable C++ revision contains count_for_length, solve and run_checkpoints. It is the implementation record for this article.

Problem 145 source code

C++

#include <array>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>

namespace {

using u64 = std::uint64_t;

struct Options {
    u64 limit = 1000000000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10ULL + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

u64 pow10_u64(int e) {
    u64 v = 1;
    for (int i = 0; i < e; ++i) {
        v *= 10ULL;
    }
    return v;
}

int digits_count(u64 n) {
    int d = 0;
    do {
        ++d;
        n /= 10ULL;
    } while (n > 0);
    return d;
}

u64 count_for_length(const int length) {
    if (length <= 1) {
        return 0;
    }

    std::array<int, 19> outer_count{};
    std::array<int, 19> inner_count{};

    for (int a = 1; a <= 9; ++a) {
        for (int b = 1; b <= 9; ++b) {
            ++outer_count[static_cast<std::size_t>(a + b)];
        }
    }

    for (int a = 0; a <= 9; ++a) {
        for (int b = 0; b <= 9; ++b) {
            ++inner_count[static_cast<std::size_t>(a + b)];
        }
    }

    const int half = length / 2;
    std::array<int, 10> sums{};
    u64 total = 0;

    const auto apply_sequence = [&](const int center_twice, const u64 weight) -> u64 {
        int carry = 0;

        for (int i = 0; i < length; ++i) {
            int pair_sum = 0;
            if ((length % 2) == 1 && i == half) {
                pair_sum = center_twice;
            } else {
                const int idx = (i < half) ? i : (length - 1 - i);
                pair_sum = sums[static_cast<std::size_t>(idx)];
            }

            const int digit = (pair_sum + carry) % 10;
            if ((digit % 2) == 0) {
                return 0;
            }
            carry = (pair_sum + carry) / 10;
        }

        if (carry > 1) {
            return 0;
        }

        return weight;
    };

    const auto dfs = [&](auto&& self, int idx, u64 weight) -> void {
        if (idx == half) {
            if ((length % 2) == 0) {
                total += apply_sequence(0, weight);
            } else {
                for (int middle = 0; middle <= 9; ++middle) {
                    total += apply_sequence(2 * middle, weight);
                }
            }
            return;
        }

        for (int s = 0; s <= 18; ++s) {
            const int ways = (idx == 0) ? outer_count[static_cast<std::size_t>(s)]
                                        : inner_count[static_cast<std::size_t>(s)];
            if (ways == 0) {
                continue;
            }
            sums[static_cast<std::size_t>(idx)] = s;
            self(self, idx + 1, weight * static_cast<u64>(ways));
        }
    };

    dfs(dfs, 0, 1ULL);
    return total;
}

bool is_power_of_ten(const u64 x) {
    if (x == 0) {
        return false;
    }
    u64 v = x;
    while ((v % 10ULL) == 0ULL) {
        v /= 10ULL;
    }
    return v == 1ULL;
}

u64 solve(const u64 limit) {
    if (limit <= 1) {
        return 0;
    }

    const int max_len = digits_count(limit - 1);
    u64 total = 0;

    for (int len = 1; len < max_len; ++len) {
        total += count_for_length(len);
    }

    if (limit == pow10_u64(max_len)) {
        total += count_for_length(max_len);
        return total;
    }

    if (limit <= 10000000ULL) {
        for (u64 n = pow10_u64(max_len - 1); n < limit; ++n) {
            if ((n % 10ULL) == 0ULL) {
                continue;
            }
            u64 rev = 0;
            u64 t = n;
            while (t > 0) {
                rev = rev * 10ULL + (t % 10ULL);
                t /= 10ULL;
            }
            u64 s = n + rev;
            bool ok = true;
            while (s > 0) {
                if (((s % 10ULL) % 2ULL) == 0ULL) {
                    ok = false;
                    break;
                }
                s /= 10ULL;
            }
            if (ok) {
                ++total;
            }
        }
        return total;
    }

    throw std::runtime_error("Non power-of-10 limits above 10^7 are not supported");
}

bool run_checkpoints() {
    if (count_for_length(2) != 20ULL) {
        std::cerr << "Checkpoint failed for length 2" << '\n';
        return false;
    }
    if (count_for_length(3) != 100ULL) {
        std::cerr << "Checkpoint failed for length 3" << '\n';
        return false;
    }
    if (count_for_length(7) != 50000ULL) {
        std::cerr << "Checkpoint failed for length 7" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.limit) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 145: How many reversible numbers are there below one-billion?
# Digit-pair DFS approach: for n-digit numbers, pair digits from outside in.

def solve():
    # Counts for digit pair sums
    outer = [0] * 19  # first/last digit (1-9 each, no leading zeros)
    inner = [0] * 19  # inner digit pairs (0-9 each)
    for a in range(1, 10):
        for b in range(1, 10):
            outer[a + b] += 1
    for a in range(10):
        for b in range(10):
            inner[a + b] += 1
    
    total = 0
    for length in range(2, 10):  # up to 9 digits (< 10^9)
        half = length // 2
        
        def dfs(idx, weight, sums):
            nonlocal total
            if idx == half:
                # Check all digit sums with carries
                if length % 2 == 0:
                    check(sums, 0, weight, length)
                else:
                    for mid in range(10):
                        check(sums, 2 * mid, weight, length)
                return
            
            cnt = outer if idx == 0 else inner
            for s in range(19):
                if cnt[s] == 0: continue
                dfs(idx + 1, weight * cnt[s], sums + [s])
        
        def check(sums, center_twice, weight, ln):
            nonlocal total
            carry = 0
            for i in range(ln):
                if ln % 2 == 1 and i == half:
                    pair_sum = center_twice
                else:
                    idx = i if i < half else (ln - 1 - i)
                    pair_sum = sums[idx]
                digit = (pair_sum + carry) % 10
                if digit % 2 == 0:
                    return
                carry = (pair_sum + carry) // 10
            if carry > 1:
                return
            total += weight
        
        dfs(0, 1, [])
    
    print(total)

solve()

Java

public class Euler145 {
    static int[] outer = new int[19], inner = new int[19];
    static long total;

    public static void main(String[] args) {
        for (int a = 1; a <= 9; a++)
            for (int b = 1; b <= 9; b++)
                outer[a + b]++;
        for (int a = 0; a <= 9; a++)
            for (int b = 0; b <= 9; b++)
                inner[a + b]++;
        long ans = 0;
        for (int len = 2; len <= 9; len++) {
            total = 0;
            dfs(len, 0, 1, new int[len / 2]);
            ans += total;
        }
        System.out.println(ans);
    }

    static void dfs(int len, int idx, long w, int[] sums) {
        int half = len / 2;
        if (idx == half) {
            if (len % 2 == 0)
                check(sums, 0, w, len);
            else
                for (int m = 0; m <= 9; m++)
                    check(sums, 2 * m, w, len);
            return;
        }
        int[] cnt = idx == 0 ? outer : inner;
        for (int s = 0; s <= 18; s++) {
            if (cnt[s] == 0)
                continue;
            sums[idx] = s;
            dfs(len, idx + 1, w * cnt[s], sums);
        }
    }

    static void check(int[] sums, int ct, long w, int ln) {
        int half = ln / 2, carry = 0;
        for (int i = 0; i < ln; i++) {
            int ps;
            if (ln % 2 == 1 && i == half)
                ps = ct;
            else {
                int ix = i < half ? i : ln - 1 - i;
                ps = sums[ix];
            }
            int d = (ps + carry) % 10;
            if (d % 2 == 0)
                return;
            carry = (ps + carry) / 10;
        }
        if (carry > 1)
            return;
        total += w;
    }
}