# Project Euler

## Permuted multiples

### Problem 52

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.

Unbelievably, I was able to do this by hand in less than 30 minutes.

First, the number has to be at least 6 digits to be able to satisfy the criteria because each of the multiples are a permutation of the original number. Since we are looking for the smallest, I start with 6 digits and thinking that I will have to worry about 7 digits later. Turn out the answer is a 6 digits integer.

Next, the first digit must be 1 or it will become 7 digits at 5x if it is greater than 1.

` x: 1 _ _ _ _ _`

Now, if we have only 6 digits, and the first digit is 1, the last digit must be 7 because 2,4,5,6,8 will give us a zero at some point for the unit digit which is impossible for a 6 digits integer to start with zero as one of the permutation, and the multiple of 3 or 9 will never produce 1 as the last digit in any of the multiples.

` x: 1 _ _ _ _ 7`

In fact, since we know the last digit is 7, we also know that 1,2,4,5,7, and 8 are the digits we must work with because those are the unit digit produced by 7’s multiples. The order of those last digits from 1x to 6x are 7, 4, 1, 8, 5, and 2. We also know that the order of the first digits must be 1, 2, 4, 5, 7, 8 because the first digit must grow in sequence.

``` x: 1 _ _ _ _ 7
2x: 2 _ _ _ _ 4
3x: 4 _ _ _ _ 1
4x: 5 _ _ _ _ 8
5x: 7 _ _ _ _ 5
6x: 8 _ _ _ _ 2```

Now, working from 1x to 2x, we know that the 2nd digit must not carry because 1st digit must be 2 at 2x. Therefore, 2 or 4 must be the 2nd digit in the original number. We also know that 4 can not be in front of 5, 7, and 8 because 4×2+1 = 9, which is not one of the digit we are working with. In another word, 4 must be in front of 2. Therefore

``` x: 1 4 2 _ _ 7
2x: 2 8 5 _ _ 4```

Both combination of 5, 8 work from 1x to 2x. However, if the original 5th digit place is 8 and last digit is 7, then it will produce 3×8+2 = 6 at 3x, which is not one of the digit we are working with again. Therefore,

` x: 1 4 2 8 5 7`

Continue to multiply x up to 6x will find that this number works and it is the smallest positive integer that works.