Project Euler 145: How many reversible numbers are there below one-billion?

Project Euler 145: How many reversible numbers are there below one-billion?

Written by on 20 April 2013

Topics: Project Euler

In Problem 145 of Project Euler we move away from Geometry and over to number theory again, with a problem which reads

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 (109)?

This one is insanely easy to write a brute force method and that is the first thing I did. However, as we shall see there is a more analytic approach to the problem as well.

Brute force

The brute force solution I wrote simply reverses the number, adds it to the original and then checks it, in one function which looks like

private bool isReversible(long n) {

    long number = n;

    //Check 0 in the end
    if (n % 10 == 0) return false;

    //Reverse the number
    long reversed = 0;
    while (number > 0) {
        reversed = 10 * reversed + number % 10;
        number /= 10;
    }

    //Add the original and reversed
    reversed += n;

    //Check if all digits are odd
    while (reversed > 0) {
        if ((reversed % 10) % 2 == 0) return false;
        reversed /= 10;
    }

    return true;
}

And then we can run this in a simple loop like this

int count = 0;
int limit = 1000000000;
for (long i = 1; i < limit; i++) {
    if (isReversible(i)) count++;
}

The problem with this approach is that it takes 141 seconds to finish. Of course we can rather easily speed it up by noticing that any odd number must start with an even number and vice versa. That means we only have to loop through the odd numbers and multiply it with two. Which speeds it up to only take 76 seconds (this is also included in the source code). Almost below the one minute limit, but far from what is acceptable.

Which leads us to take another approach

Analytic solution

I sat down with pen and paper to analyse the different scenarios. I started by investigating the different number of digits to find a pattern, which I could support by results from the brute force solution.

I will go through each number of digits in the problem and then make a generalisation into three categories.

1 digit

It is easy to see that any one digit number will add to itself, which always ends up being an even number. And thus there are no solutions

2 digits

If we have two digits ab then we will end up with solution consisting two digits with a+b. These both have to be odd. If a+b > 10 then we have a carry over and thus the first digit of the result will have a different parity than the second digit. Therefore we can only form solutions where a+b < 10 and a+b is odd.  I am not exactly sure how to make an analytic solution for this. But writing them all out gave be 20 solutions. Same thing as my brute force solution

3 digits

In the three digit case we once again have that the middle digit needs to be added to it self. That means that the third digit must have a carryover and be odd.

Since the third digit is odd the first digit is odd as well if the second digit does not have a carry over, which happens when the second digit is less than 5, which gives us 20 choices for the first/third digit set and 5 options for the middle. Which totals 100 pairs

4 digits

Here we have two pairs, which I will denote the inner and outer pair. If the inner pair have carry over then the outer pair must also have carry over. Since otherwise the two inner pairs will have different parity. However, if the inner pair have carry over then the outer pair will have different parity since the first digit will end up with a carry over which the last digit wont get. Therefore we have solutions only when none of the pairs have carry over.

For the outer pair this gives us the 20 choices we have seen in the two digit case.  And it gives us 30 cases for the inner pair, since they can also contain a zero.

Or in total we get 20*30 = 600 solutions

5 digits

Here we have the middle digit, the inner pair and the outer pair.

The middle digit adds to it self, which means that the inner pair must have a carry over. When the inner pair have a carry over that means the outer pair will have a different parity. And thus there are no solutions.

6 digits

You can make the exact same argument as in the 4 digit case, but with one extra pair.  So if we have the inner, middle and outer pair. We can see that if the inner pair have a carry over then the middle pair must have a carry over as well and that leads to the outer pair having different parity. So that means that none of the pairs can have a carry over.

So we have that the inner and middle pair have 30 options each and the outer pair have 20 options. So in total 20*30^2 = 18.000

7 digits

In this case we have the middle digit, inner pair, middle pair and outer pair.

The middle digit needs a carry over, since it adds to it self. So that means the inner pair must have a carry over.

This in turn means that there will be a carry over to the middle pair from the inner pair which will need to be even on its own.  Which in turn leads us to conclude that the outer pair must have a carry over. Also the middle pair can’t have a carry over since that would lead the outer pair to have different parity.

So the outer pair must have a carry over and be odd and not include 0. That gives it 20 options

The middle pair must be even and not have a carry over. This gives us 25 options

The inner pair must be odd and have a carry over. This gives us 20 options

The middle digit must not have a carry over so that gives us 5 options.

So that is a total of 20*25*20*5 = 50.000 solutions

8 digits

We can carry the same argument as in the 6 digit case so that gives us

20*30^3 = 540.000

9 digits

This is the really big one with lots of numbers in, so this is also the most important one

We have four pairs and a middle digit. I will number the four pairs 1,2,3,4 since using inner and outer might get a bit confusing.

The middle digit must as always get a carry over, so pair 4 must have a carry over.

If pair 4 has a carry over it will deliver a carry over to pair 3 and thus, pair 2 must also deliver a carry over to pair 3.

If pair 2 have a carry over then pair one will receive a carry over which means that it will end up with different parities. So we can conclude that there are no solutions in this case.

Generalizing the solutions

All even numbered digits have the same formula so we can generalize that for some integer k such that n = 2k we have 20*30^(k-1) solutions. Which represents the outer pair along with all the inner pairs.

3 and 7 have the same kind of argumentation, and I have carried it out on 11 as well just to check. So for a number n = 4k + 3 for some integer k we have that the middle digit and the outer pair gives us 5 and 20 options.

Then we have sets of internal pairs which gives us 20 and 25 solutions. So that means we can generalize it to 20*5*(20*25)^(k-1) = 100*500^(k-1)

Then in order to have covered all numbers we need to cover n = 4k+ 1 which means 1, 5, 9,… and none of these have solutions.

So there you have it. A set of simple formulas that can be used to find the answer. I have coded that as

int count = 0;

for (int i = 1; i < 10; i++) {

    switch (i % 4) {
        case 0:
        case 2:
            count += 20 * (int) Math.Pow(30, (i / 2 - 1));
            break;
        case 1:
            count += 100 * (int)Math.Pow(500, i / 4 -1);
            break;
        case 3:
            break;
    }

}

which gives us the solution in much less than a millisecond.

Wrapping up

I am aware that the analytic solution can be a bit difficult to read at first, but if nothing else then try to sit down with pen and pencil and try it your self. You will realize that the argumentation isn’t that difficult after all.

You can find the source code here.

5 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

    Table 1
    Variation in the total of reversible numbers as the integer limits increase.

    http://img15.hostingpics.net/pics/737855pe145tab1.jpg

    Table 1 shows that there is no increase in reversible numbers between 10 000 and 100 000. Same results between 100 000 000 and 1 000 000 000.
    A list of reversible numbers is available on OEIS site:
    A135739 Numbers n such that n+reverse(n) has only odd decimal digits
    (n not multiple of 10).
    http://oeis.org/A135739
    http://oeis.org/A135739/b135739.txt

    ___

    Sources:

    1) Project Euler 145
    Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem145.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  2. Wrathchild says:

    I’ve been trying to think of a method to decompose a number M into a number N which, added to its reverse Nr, equals that first number (N +Nr = M). For example 685 decomposes into 392+293. M can be any number between 1 and 10^(100000). Is there an efficient method to start with a number like 685 and find 392?
    Thank you

  3. Freud says:

    Doesn’t case “1” (in which the remainders are 1) have no solutions and case “3” have solutions?

    Are the switched around accidentally?

  4. Refai says:

    // my solution in a different way

    public class Euler145 {

    public static void main(String[] args) {

    int i, j, add, convert, count = 0;
    String get;
    StringBuilder rev;

    for ( i=0; i 0) {
    j = add % 10;

    if (j == 1 || j == 3 || j == 5 || j == 7 || j == 9) {
    add /= 10;
    String leadZero = “” + i;
    if (j == 0 && !leadZero.endsWith(“0”)) {
    count++;
    }
    } else {
    break;
    }
    }
    }
    }
    System.out.println(count);
    }
    }

  5. Refai says:

    Use for loop
    for (i =0; i <= 1000000000; i++)

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.