# Project Euler | The Millionth Lexicographic Permutation Of The Digits

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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.