Problem D
Lucky Numbers

Photo by Chris Smith.

Mr. Lucky has a store that sells numbers. These numbers have an interesting property: each number formed by its first $k$ digits is evenly divisible by $k$, for $k$ from $1$ to $n$, where $n$ is the number of digits in the number. The numbers do not have leading zeroes.

Mr. Unlucky wants to open a competing store. Price for lucky numbers is driven by demand and supply, and given by the formula

\[ \mbox{price} = \frac{\mbox{demand}}{\mbox{supply}} \]

while demand for numbers with $n$ digits is given by the formula

\[ \mbox{demand} = \mbox{citySize} \cdot \mbox{dayOfMonth} - n^ e \]

where $e$ is the base of the natural logarithm. Supply for lucky numbers with $n$ digits is simply the number of lucky numbers with $n$ digits. Help Mr. Unlucky calculate the supply for $n$ digit lucky numbers.


The input is a single integer $n$.


Output the supply for $n$ digit lucky numbers.


  • $2 \leq n \leq 1\, 000$

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2

Please log in to submit a solution to this problem

Log in