Project Euler 52: Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order

Project Euler 52: Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order

Written by on 16 July 2011

Topics: Project Euler

Problem 52 of Project Euler reads

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Between solving this problem and writing this text I did a bit of research on other peoples solutions. It seems that some people already knew the answer from an old high school exercise with fractions or from the book The man who counted by Malba Tahan. The book cover of that book is used for this posts headline image. I must admit that I didn’t know that. Apparently I could have just asked Wikipedia for the answer.

So based on my apparently limited knowledge on this problem I went for the brute force solution.

Analysis of the Problem

One thing to note is that we are looking for a number x such that 6x contains the same digits. That means the same number of digits as well. So for any decade n we are searching through we only need to search the n*10/6 first numbers. So for two digit numbers we only need to search 10-16 since 17*6 = 102 and thus cannot contain the same digits.

That was all I was able to deduce about the problem.

Coding the Solution

The first thing we need in order to get a solution is a way to figure out if two numbers are permutations of each other. Luckily we already have a function for doing that which we made in Problem 49. So I wont go through it here. You can of course find the method in the source code or peek at the solution for Problem 49.

Once we have a method for checking permutations the solution can be implemented as

int start = 1;
bool found = false;
int result = 0;

while (!found) {
    start *= 10;
    for (int i = start; i < start * 10 / 6; i++) {
        found = true;
        for (int j = 2; j <= 6; j++) {
            if (!isPerm(i, j * i)) {
                found = false;
                break;
            }
        }
        if (found) {
            result = i;
            break;
        }
    }
}

This piece of code does not make any assumption of how many digits we need to find the number except that we need more than 1.

Executing the C# code above gives the following result

First number to contain the same digits is 142857
Solution took 9 ms

I am fairly satisfied with the result. Limiting the search in each decade cut the search time significantly.

Wrapping up

The problem was a quick and easy one to solve, and didn’t give me too much challenge. On the other hand, my chosen solution was a brute force one, so I might very well have missed some obvious improvement. If you have any tips or tricks on how to improve the solution, I would be very glad to hear from you. Questions and comments are of course more than welcome as well.

As usual you can find the source code for download.

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

  1. SuprDewd says:

    I’ve always wondered why the solution isn’t 1. 🙂

  2. SuprDewd says:

    Scratch that. I got a bit confused.

  3. zhilongji says:

    since x and 3x have the same digits,x%3 == 0 will always be true,so we can search with the start as 10^i+2,and the step as 3.

  4. Kristian says:

    Hi Zhilongji

    You are right, since if a number is divisible by three the digit sum will also be divisible by three. And since 3x and x have the same amount of digits x must be divisible by 3 as well.

    And thus you are right. We can start search with 12, 102, 1002 and so on, as well as we can increase the search with 3 for every step.

    It changes the code to

    int start = 1;
    bool found = false;
    int result = 0;
    
    while (!found) {
        start *= 10;
        for (int i = start+2; i < start * 10 / 6; i+=3) {
            found = true;
            for (int j = 2; j <= 6; j++) {
                if (!isPerm(i, j * i)) {
                    found = false;
                    break;
                }
            }
            if (found) {
                result = i;
                break;
            }
        }
    }
    

    And it executes on my computer in 3ms, or a speedup of a factor 3, which is sort of expected since we reduce the search space with a factor of 3.

    Very well thought of and thanks a lot for sharing that insight.

    /Kristian

  5. Ehsan says:

    Hi,
    you can also start from 100,000 to check numbers because the first digit of x, 2x, 3x, 4x, 5x, 6x is different .

    but there is no difference in execution time in my computer.
    thanks for the great blog!

  6. Euler says:

    Since a number and any of its permutations always differ by a multiple of 9, we can say that (2x-x) should be a multiple of 9, ie x is a multiple of 9. Hence, the loop can be incremented by 9 instead of 1 or 3.

  7. mappo says:

    Could you make use of the fact that 5*n always will end in a five or a zero i.e. there will have been a five or a zero in n?

  8. LL says:

    In my view, the code can be modified as this:

     int start = 1;
        bool found = false;
        int result = 0;
        
        while (!found) {
            start *= 10;
            for (int i = start+2; i < start * 10 / 6; i+=15) {
                found = true;
                for (int j = 2; j <= 6; j++) {
                    if (!isPerm(i, j * i)) {
                        found = false;
                        break;
                    }
                }
                if (found) {
                    result = i;
                    cout<< result<<endl;
                    break;
                }
            }
        }
    

    My assumption is that 5*n always will end in a five or zero. So the testing number should be added in a step of 5. But it should also meet the condition of multiple of 3. So it makes the step change to 15.

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.