Published on

Project Euler | The Millionth Lexicographic Permutation Of The Digits

Authors

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.