The 24th problem of Project Euler wanted the one-millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
This was yet another problem which I solved with paper and pencil.
We determine one digit at a time. Say the most significant digit is x, then the remaining 9 digits can fill up the remaining places of the 10 digit number. This can be done in 9! = 362880 ways.
362880 X 2 < 1000000 < 362880 X 3
This implies that all the numbers with 0 and 1 as the most significant digits make up 362880 X 2 numbers, which is less than a million, and when we start with 2 as the most significant digit, the one millionth number comes before the series is over. Thus our first digit is 2.
Now with that fixed, we need to find the 1000000 – 2 X 362880 = 274240th number arranged lexicographically using digits 0, 1, 3, 4, 5, 6, 7, 8 and 9. This time we need to consider 8! = 40320.
40320 X 6 < 274240 < 40320 X 7
Thus we need the 7th digit which is 7. So our number starts with 27.
The same step is to be repeated over and over again. In a condensed notation, the digits found are:
9! X 2 < 1000000 < 9! X 3 => digit is 2; 1000000 – 725760 = 274240
8! X 6 < 27420 < 8! X 7 => digit is 7; 27420 – 241920 = 32320
7! X 6 < 32320 < 7! X 7 => digit is 8; 32320 – 30240 = 2080
6! X 2 < 2080 < 6! X 3 => digit is 3; 2080 – 1440 = 640
5! X 5 < 640 < 5! X 6 => digit is 9; 640 – 600 = 40
4! X 1 < 40 < 4! X 2 => digit is 1; 40 – 24 = 16
3! X 2 < 16 < 3! X 3 => digit is 5; 16 – 12 = 4
At this point the digits left are 0, 4 and 6. The 4th number ordered lexicographically will be 460.The number we set out to find is thus 2783915460.
Popularity: 41% [?]
Related posts:
