// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 52 Solution

Project Euler 52 Solution

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


Problem Description

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.

Analysis

This is a rehash of an old high school problem on repeating digits:

1/7 = 0.142857 142857 142857 ...
2/7 = 0.285714 285714 285714 ...
3/7 = 0.428571 428571 428571 ...
4/7 = 0.571428 571428 571428 ...
5/7 = 0.714285 714285 714285 ...
6/7 = 0.857142 857142 857142 ...

I’m sure you get the idea without giving away the answer.

As for our programmatic solution: an assumption that the digits didn’t have to be unique, I set the number of digits less one as our starting bound and search sequentially by sorting the digits within each number and comparing for multiples 1, 2, 3, 4, 5 and 6.

We can begin our search with a 5 digit multiple of 9, such as 99999, because the result has at least 6 digits. Also, because any number and its permutation always differ by a multiple of 9 (ex., (45121-11542)/9 = 3731) we can increment by 9 instead of 1.

Project Euler 52 Solution

Runs < 0.015 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 52 Solution Python 2.7 source.

Afterthoughts

  • The next one found was 1428570
Project Euler 52 Solution last updated

Discussion

One Response to “Project Euler 52 Solution”

  1. How can we say that the result must contain at least 6 digits?

    Posted by Sagnik | June 18, 2019, 11:38 PM

Post a comment