Not That Easy

The number of 7-digit numbers with 1 in the left most place and containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once is 6! = 720. But 120 of these end in 5 and hence are divisible by 5. Thus the number of 7-digit numbers with 1 in the left most place and containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once but not divisible by 5 is 600. Similarly the number of 7-digit numbers with 2 and 3 in the left most place and containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once but not divisible by 5 is also 600 each. These account for 1800 numbers. Hence 2000-th number must have 4 in the left most place. Again the number of such 7-digit numbers beginning with 41,42 and not divisible by 5 is 120 − 24 = 96 each and these account for 192 numbers. This shows that 2000-th number in the list must begin with 43. The next 8 numbers in the list are: 4312567, 4312576, 4312657, 4312756, 4315267, 4315276, 4315627 and 4315672. Thus 2000-th number in the list is 4315672.

Create an increasing list $L$ of our seven-digit numbers. The list index starts with zero , so we want to find $L_{1999}$ . Name the the digits of any number $N$ in the list. The last digit must not be 5, otherwise $N$ would be divisable by 5: $N\overset{!}{=}(d_6,\ldots,\:d_0),\qquad d_0\neq 5$

The first digits are most significant - let's count the choices $n_k$ we have if we fix the first digits $d_6,\ldots,\:d_k$ . If the digit 5 is not among the the higher digits, we have $k-1$ choices for $d_0$ and then $(k-1)!$ choices for the rest: $\begin{aligned} n_k&=\begin{cases} k!&5\in\{d_{6},\:\ldots,\:d_k\}\\[.25em] (k-1)\cdot(k-1)!&\text{else} \end{cases} \end{aligned}$

Observe that our list-index can be partitioned using $n_k$ : $\begin{aligned} 1999&=3\cdot 600+2\cdot 96+0\cdot 18+1\cdot 4+1\cdot 2+1\cdot 1\\[.5em] &=\red{3}\cdot 5\cdot 5!+\red{2}\cdot 4\cdot 4!+\red{0}\cdot 3\cdot 3!+\red{1}\cdot 2\cdot 2!+\red{1}\cdot 2!+\red{1}\cdot 1!+\red{0} \end{aligned}$

Similar to "decimal-to-binary" transformations, the red numbers tell us which index of the remaining smallest digits we have to choose for $d_k$ . The following table shows the iterations: $\begin{aligned} \begin{array}{rr|rrrrrrr} d_6:&\red{3}& 1& 2& 3& \blue{4}& 5& 6& 7\\ d_5:&\red{2}& 1& 2& \blue{3}& & 5& 6& 7\\ d_4:&\red{0}&\blue{1}& 2& & & 5& 6& 7\\ d_3:&\red{1}& & 2& & & \blue{5}& 6& 7\\ d_2:&\red{1}& & 2& & & & \blue{6}& 7\\ d_1:&\red{1}& & 2& & & & & \blue{7}\\ d_0:&\red{0}& & \blue{2}& & & & & & \end{array} &&&\Rightarrow&&&&L_{1999}=\boxed{4315672} \end{aligned}$

The number of 7-digit numbers with 1 in the left most place and containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once is 6! = 720. But 120 of these end in 5 and hence are divisible by 5. Thus the number of 7-digit numbers with 1 in the left most place and containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once but not divisible by 5 is 600. Similarly the number of 7-digit numbers with 2 and 3 in the left most place and containing each of the digits 1, 2, 3, 4, 5, 6, 7 exactly once but not divisible by 5 is also 600 each. These account for 1800 numbers. Hence 2000-th number must have 4 in the left most place. Again the number of such 7-digit numbers beginning with 41,42 and not divisible by 5 is 120 − 24 = 96 each and these account for 192 numbers. This shows that 2000-th number in the list must begin with 43. The next 8 numbers in the list are: 4312567, 4312576, 4312657, 4312756, 4315267, 4315276, 4315627 and 4315672. Thus 2000-th number in the list is 4315672.