|
3,782,915,460
DECLARE SUB permute (a$)
CLS
n$ = "1023456789"
FOR i = 1 TO 999999
permute n$
NEXT
PRINT n$
The computer solution agrees with the following analytic solution.
Analytic method:
The factorials needed are:
9 362880
8 40320
7 5040
6 720
5 120
4 24
3 6
2 2
1 1
There are 9! pandigitals starting with 1 and the same number starting with 2, and likewise 3. So the millionth starts within the third group of 362880, and thus the number begins with a 3.
The last pandigital starting with 2 was the 725760'th (twice 362880), leaving 274240 to go.
274240/40320 is 6 with 32320 left over. So for the second digit, we bypass the first 6 possibilities: 0, 1, 2, 4, 5, and 6, making the second digit 7 (remember, the second digit couldn't be 3 if that's the first digit).
Then, 32320/5040 = 6 with 2080 left over, so the third digit bypasses 0, 1, 2, 4, 5, and 6 and is the next available digit: 8. So far we have 378.
2080/720 is 2 with 640 remaining. Bypass 0 and 1 and take 2 as the next digit. We now have 3782.
640/120 = 5 with remainder 40. Bypass 0, 1, 4, 5 and 6 out of the remaining digits and take the next remaining digit: 9. So far we have 37829.
40/24 = 1 with remainder 16, so skip only the 0 and take the 1: we now have 378291.
16/6 = 2 with remainder 4. Skip 0 and 4, and take the next still available: 5. We now have 3782915.
4/2 = 2 with no remainder. Since there's no remainder, the millionth pandigital is the last pandigital that has the second remaining digit as the next one after the 5. The remaining digits are 0, 4 and 6, so the second is 4 and the number sought begins 37829154. The last such pandigital must the the highest possible with the two remaining digits: 3782915460.
|
