I Need 2016 Numbers With Repeated Digits

We claim that $n=\boxed {4490}$ is the answer. Let $f(n)$ denote the number of numbers with at least one repeating digit in $S$ . A natural way to find $f(n)$ is to count the number of numbers with no repeating digits in $S$ , then subtract that number from $n$ .

We first compute $f(3999)=3999-(9+9^2+9^2\cdot 8+3\cdot 9\cdot 8\cdot 7)=1749$ . (There are $9$ one-digit numbers with distinct digits, $9^2$ two-digit numbers with distinct digits, so on.)

Next we find $f(4399)$ , which is just $1749$ plus the number of repeating digit numbers in $[4000,4399]$ . Note that $4$ cannot be used for the last three digits, therefore this range contains $400-4\cdot 8\cdot 7=176$ of those numbers. (There are $4$ choices for the third digit- $0,1,2,3$ , $8$ choices for the second digit, so on.) Thus $f(4399)=1749+176=1925$ .

Since all numbers in $[4400,4499]$ contain two $4$ 's, $f(4399+n)=1925+n$ . Hence $f(4490)=f(4399+91)=1925+91=2016$ .

Hi Xuming Liang,

Thank you for taking the time to solve my problem and posting a solution. The way you solved the problem is an example that is - in my opinion - perfectly acceptable sometimes, which is: "Finding a solution without actually having a general formula which can be applied to all numbers."

Your reasoning is very clear!

Kind regards, Patrick