Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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.

share|improve this question
    
What was this an interview for? –  CommonerG May 9 '13 at 10:51

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
You are not wrong. But you haven't answered the question. –  TonyK May 9 '13 at 11:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.