Loading...
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.
Use this link to get the Project Euler 52 Solution Python 2.7 source.
Afterthoughts
- The next one found was 1428570
How can we say that the result must contain at least 6 digits?
Posted by Sagnik | June 18, 2019, 11:38 PM