5
$\begingroup$

$f(n)$ is a function counting all the ones that show up in the sequence $1, 2, 3, ..., n$.

IE $f(1)=1$, $f(10)=2$, $f(11)=4$ etc. Discounting the trivial case $f(1) = 1$, when is the first time $f(n)=n$?

I found this on an interview question. I was wondering if there were any clever ways to think about this mathematically/cleverly other than brute-forcing the problem.

Thanks.

  • 0
    What was this an interview for?2013-05-09

2 Answers 2

6

The next is 199981. These numbers are given in A014778. One way to think of it is in decades. Up to 99999, (if you prefix 0's to make each number 5 digits) each digit equidistributed. So you get 10^4 1's per place, or 5E4 1's total, and are short 50,000 1's. But then going up to 199,999 you get 100,000 1's from the first place plus the 50,000 from the other places, so you are 1 ahead. So back up until you give up another extra 1, which gives 199,990 and its predecessors down to 199,981.

0

From $1$ to $99,999$, there are $50,000$ $1$'s.

From $100,000$ to $199,999$ there are $50,000$ $1$'s [not at the first digit] plus another 100,000 1's at the first digit.

So from $1$ to $200,000$ there are a total of $200,000$.

Correct me if i am wrong.

  • 0
    You are not wrong. But you haven't answered the question.2013-05-09