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.

Define $f:\mathbb{N}\rightarrow\mathbb{N}$ as follows, $f(n)$ is the number of times the digit "1" is needed if we were to write all integers between 1 and $n$ (inclusive) in base 10. So for example

$f(1)=1$

$f(2)=1$

$f(3)=1$

...

$f(9)=1$

$f(10)=2$

$f(11)=4$

$f(12)=5$

...

$f(99)=20$ and so on. Clearly $f(1)=1$ is a fixed point. The original question was to find the next fixed point. I immediately established the recursive relation

$$f(10^k-1)=10\cdot f(10^{k-1}-1)+10^{k-1}$$

with $f(9)=1$. Then I got the explicit relation

$$f(10^k-1)=k\cdot 10^{k-1}.$$

So we see that after $n=1$, $f(n)<n$ until we get to $f(9,999,999,999)=10,000,000,000$ so the fixed point must be between one billion and ten billion. Then after carefully counting and keeping track of what I was doing I got the fixed point to be

$$f(1,111,111,110)=1,111,111,110.$$

Now my questions are

  1. Does anyone know the origin of this problem? Like is it a Putnam/IMO/etc... challenge problem? I originally heard this problem way long ago when starting my undergrad and I just randomly remembered it again a few days ago.

  2. Is there an elegant or an easier way of doing this analytically?

  3. Since I don't know how I heard of this problem...and it is a data retrieval nightmare (like when I try to google it), I have no idea if my solution is right or not. Can someone perhaps verify it? I can't tell if I made a mistake counting or not.

  4. Is it possible to code this efficiently so that I can get an answer by a simulation? From what I remember I tried MATLAB and Mathematica but it just took so frigging long I had to kill them without knowing the answer and go back to paper and a pencil. I didn't try C++ or FORTRAN. In Mathematica I did try to "optimize" it as much as I could using its built-in functions but too slow. For MATLAB, I couldn't see how to vectorize it so just had to write a loop which is of course a bad idea. Any efficient algorithms? Any ideas?

  5. More of a theoretical question, is there any way to prove that another fixed after $n=1$ even exists over $\mathbb{N}$? Using the recursive relation above we see that

$f(999,999,999)=900,000,000$

and

$f(9,999,99,999)=10,000,000,000$

so $f(n)>n$ and then I just narrow the interval until I get $f(n)=n$. If we considered the smooth continuation of $f(x)$ over $\mathbb{R^+}$ then yes the intermediate value theorem guarantees us the fixed point ($f(x)-x$ has an $x$-intercept because it switches sign). But how do we know, how can we prove that the fixed point is EXACTLY on an integer? I mean I know the answer must exist because the question was posed but frankly I am a little surprised that there is another integer after one where the integer exactly equals the number of times "1" is needed to get there.

6.Can we say anything about the long term behavior of $f$? Like will $f(n)$ be always greater than $n$ after the second fixed point or will it oscillate going above and below $n$ arbitrarily many times as $n$ tends to infinity? Are there any other fixed points? Are there any other fixed points over the natural numbers? Any way to find them all? Does the smooth continuation of $f$ to the reals have a closed form expression? What would it be?

Thanks!

share|improve this question
    
Sorry, your "number of 1 required to write $n$" doesn't make any sense, and your list of values even less. –  vonbrand Jan 23 '13 at 2:52
    
To find $f(12)$ for example, concatenate all integers from 1 through 12 like this 123456789101112 and then count how many times does the digit "1" occur in this string. Therefore $f(12)=5$. –  Fixed Point Jan 23 '13 at 4:17
add comment

2 Answers 2

up vote 1 down vote accepted

What a long question!

I'll just answer some of your questions. I think I have already seen a problem similar to this on projecteuler. Since it's more a programming website, I would answer to your second question saying that there is no elegant way to do it... But as you saw, we can easily have the value of $f(10^k - 1)$. Actually, it's not necessary to do a recursion. If you think about it, $f(10^k - 1)$ is the number of numbers with $k$ digits or less which have a $1$ in first position, plus the number of those with a $1$ in second position, and so on... And the number of numbers with at most $k$ digits, with a $1$ forced in a position, is $10^{k-1}$ (you put what digit you want in other places). And you do it $k$ times so you get $f(10^k - 1) = k\cdot 10^{k-1}$.

Note that it's not so obvious that the next fixed point is between one billion and ten billion. Indeed, you have

$f(99,999,999) = 80,000,000$ and $f(999,999,999) = 900,000,000$

but you could have for example $f(555,555,555) = 555,555,555$... Even it seems not likely, you would have to prove it.

You could check that your solution is indeed a fixed point, and if it's one, it's oviously the first after $1,000,000,000$. To do it, do with the same method that the one I used for $10^k - 1$. Actually, you'll see that the number of numbers $\leq 1,111,111,110$ that have a $1$ in $i$-th position is $111,111,111$, for any $1\leq i \leq 10$. So

$f(1,111,111,110) = 10\cdot111,111,111 = 1,111,111,110$

as you want.

Also, you can see that for all $k \geq 100$, $f(10^k-1) = k\cdot10^{k-1} \geq 10^{k+1} > 10^{k+1}-1$. As a consequence, there is no fixed point after $10^{100}-1$ since

$f(10^{100}-1) > 10^{101}-1$

$f(10^{101}-1) > 10^{102}-1$

and so on, and $f$ is clearly increasing.

I'll also give you an idea to code it. If you search the first fixed point after $n$, you do a recursion like this : Start with $n$ and compute $f(n)$ with the method I mentionned (it's not super easy to calculate but it's possible differentiating some cases).

If $f(n) = n$, you have found your fixed point.

If $f(n) > n$, there is no fixed point before $m = f(n)$, so restart with $m$.

If $f(n) < n$, calculate the least number $m$ greater than $n$ such that $f(m) > n$. For example, if $n = 99$, $f(99) = 20$ and you know that your fixed point will have a value greater than $99$ so you search the number $m$ such that $f(m) \geq 100$. And you restart with $m$. Well, it's not easy to code, but I think it could perform.

Lastly, it seems a bit ambitious to me to talk about a smooth continuation of $f$... Mathematics is not so beautiful :(

I hope it will help you ;)

share|improve this answer
    
Thanks for the long answer to my long question ;-) Pleas see my answer below. Since you are the only one who posted something, you get the check. –  Fixed Point Jan 4 '13 at 8:00
add comment

Well, in case anyone is interested, after doing a bit of research I've found out that the problem I posted, was on Google job interviews. Applicants would be asked to solve this on the spot (by programming I am assuming). It also turns out that this is a very small part of Project Euler problem #156. The statement of which suggests that this function can be defined for any of the nine nonzero digits. For each digit you have more than one fixed points but only finitely many. In addition, the same number can be a fixed point for more than one digit simultaneously.

Furthermore, the answer I found to my problem was wrong. The acceptable answer at google...and the first fixed point after 1 is actually 199981. My number is a fixed point but not the second smallest one. Guess I won't be working at google then ;-).

share|improve this answer
add comment

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.