11
$\begingroup$

We have a function:

$f(n)$ = number of occurrences of the digit $1$ in the numbers from $0$ to $n$.

Example: $f(12) = 5$

It is obvious that $f(1)=1.$

Question: Which is the next number for which $f(n) = n$?

  • 0
    111111111111111111111111111111111112879812011-06-24
  • 0
    How did you come up with that number?2011-06-24
  • 0
    Why f(12) is not 4? 1 10 11 12 EDIT: ok I realize that 11 counts double!2011-06-24
  • 1
    @S4M: count the 1 in 12 as well.2011-06-24
  • 0
    @S4M: I think f(n) *includes* n. @Mark: Can you give me a little more background before I reveal my secrets? Were you assigned this problem?2011-06-24
  • 0
    @Isaac: Where did your answer go? I was going to ask for some clarification...2011-06-24
  • 0
    @The Chaz: Yes, a friend of mine gave me this problem (riddle?). I don't know anything more about it.2011-06-24
  • 0
    @TheChaz: I thought about it for another minute and realized that it didn't actually prove the result, so I deleted it. (I'm fairly confident that $f(10^k-1)=k\cdot10^{k-1}$ is correct, but from that and that $f$ is nondecreasing isn't a quick jump to there being no such $n$ other than 1.)2011-06-24
  • 0
    @Isaac: What about induction on intervals {$10^k, 10^k + 1, ..., 10^{k + 1} - 1$} ?2011-06-24
  • 1
    @Mark: The number in my first comment was meant to stir the pot; I don't think there is another solution.2011-06-24
  • 0
    @TheChaz: The problem isn't in extending the result, but rather that knowing $f(10^k-1)=k\cdot10^{k-1}$ for, say, $k=7,8$ doesn't actually imply that there isn't some $10^7-1$f(n)=n$. – 2011-06-24
  • 1
    Wouldn't potential solutions to this be more likely/frequent, say, in base 2? ;-)2011-06-24
  • 0
    This is a not-so-veiled attempt to elicit a solution to a project euler problem.2011-06-24
  • 0
    I had seen this problem years ago, had fun with it and sent it to Euler. Can you prove there are only a finite number of solutions?2011-06-25
  • 0
    In what base???2011-06-27
  • 0
    Can I write a program to solve it?2011-06-24
  • 0
    @bol1024: I deleted your answer, which was really a question, and turned it into a comment. Please do not use the answer box to ask question :) You should probably add your "Can I write a program to solve it?" to the body of the original question by editing it or add it as a comment to an answer, if that is more to the point.2011-06-27
  • 0
    Maybe $n \mod 10^j$ instead of n[j:] ? And what about $d=0$ in $f(0,n) = n$ ? I found solutions $f(d,n) = n$ for $1\le n\le 9$ (OEIS A014778, ...) but nothing for $d=0$.2012-10-23
  • 0
    Check out [Count the number of Ks between 0 and N?](http://stackoverflow.com/q/20945790/2589776).2014-03-18

3 Answers 3

8

So I dug up my notes on this problem (for those interested this is project euler problem # 156) There is an analytical form for the solution to this problem (but alas, even the analytical form is too slow to solve the big problem, which requires finding ALL numbers that satisfy this condition for ALL digits 1-9). I will state my result first (to avoid hiding it in the text) and provide explanation for it after.

SOLUTION

Define a list representation of a number $n$ to be (following a notation I borrowed from continued fractions)

$$n = r_k*10^k + r_{k-1}*10^{k-1} + ... + r_0*10^0 \equiv [r_k,r_{k-1},...,r_0]$$ The function $f(d,n)$ which gives the number of occurances of a digit $d$ up to the number $n$ is given by $$ f(d,n) = \sum_{j=0}^k\left(\sum_{i=0}^{r_j} (10^j\delta_{i-1,d})+ r_jE(j) +\delta_{r_j,d}(n[j:]+1)\right)$$

where the notation $n[j:]$ is used to signify the number formed by the last $j$ digits (e.g. for $n=1234=[1,2,3,4]$, $n[1] = 4$, $n[3] = 234$) and $E(j) = j*10^{j-1}$

Typing this into mathematica (and checking ($f(1,n) = n$ gives the next result of $\mathbf{199981}$).

NOTE: This can be generalized even further to any base $B$ by replacing occurrences of $10^k$ with $B^k$

MOTIVATION

First observe that in the number 0-9 any digit appears only 1 time.

In the numbers 0-99 any digit appears 10 + 10 times (10 times as the ones digit and 10 times in the range x0-x9)

In the numbers 0-999 any digit appears 20*10+100 = 300 times (20 times in each range of 100+ plus 100 in the range x00-x99)

It is not difficult to prove that this pattern continues, for any number given as $10^k-1$ there are $k*10^{k-1}$ appearances of any digit in that range.

This motivates my definition of the function

$$E(j) = j*10^{j-1}$$

However, the number given is unlikely to be as nice as $10^k-1$ we have to learn a clever way to add up the parts of that range. For a number (given in the above notation) like $[4,0,0,0]$. We see that the range $0-999$ occurs 4 times ($0-999$,$1000-1999$,$2000-2999$,$3000-3999$. So we are left with $4*E(3) = 1200$ occurrences of the digit $1$ (this motivates the $r_jE(j)$ term). However, in the range 1000-1999 the digit one occurs an extra 1000 (or $10^j$) times, this extra term only happens if $r_j$ is greater then the digit we are summing over (e.g. if we are adding occurrences of the digit $9$ the answer would be 1200 and not 2200), the best way I could think of to express this conditional statement analytically was with the sum $\sum_{i=1}^{r_j}(10^j\delta_{i-1,d})$

Calculating a number like $[4,1,2,4]$ is not much more difficult, we simply iterate over the sequence $[4,0,0,0]$, $[3,0,0]$, $[2,0]$,$[4]$ following the formula in the previous paragraph. However, the method above will miscount because it ignores the extra occurrence of the digit $1$ in the range $4100-4124$. So at every step of the iteration we have to make sure there aren't any tails that we are forgetting to count, which motivates the $\delta_{r_j,d}(n[j:]+1)$ term.

  • 0
    Hi ! I was working over this problem 156, and came up with a similar solution (wrote a program) - but i have been struggling to find out HOW to know when to stop.. How does one know that we've exhausted all possible solutions for [f(d,n) - n = 0] ?? My program almost ran out of memory trying to figure out a pattern !!2013-08-01
  • 0
    Find a simple formula for n=9999999....9. Then note that if you have more than 10 digits you cannot have the desired equality.2017-02-22
6

Ok this is simple to do with Mathematica.

For[i = 0; j = 0, i <= 200000,
 i++, j += (Plus @@ Cases[IntegerDigits[i], 1]); If[j == i, Print[i]]]

The result is

0,1,199981,199982,199983,...,199990,200000

Therefore the number you search has to be 199981.

  • 0
    While this is a correct way to approach this particular question, the *actual* problem in question (which is a project Euler problem) requires the sum total of **all** numbers that satisfy this condition for all digits 1-10. Not so easy (or fast) do with this brute force method (where do you set the upper search limit for instance?).2011-06-24
  • 0
    You can easily make it stop after it finds the first wanted number. I leave this modification to you. I agree that with some thoughts you could still fasten up the calculation a lot (factor 100 at least).2011-06-25
  • 0
    I dont see why 199984, 199985,...,199990 are not solutions as well as we have $f(199984)=f(199983)+1=199984$ and same for every number until 199991.2011-06-25
  • 0
    You are right I didn't mark properly that I left out the other solutions, now its correct.2011-06-25
  • 1
    *fasten up the calculation* I like it. How about *slowen down the calculation*?2011-06-25
  • 0
    Seems like it was no correct english :-). I wanted to say "speed up" the calculation in case you didn't get me.2011-06-25
1

I think I have the beginning of an idea to solve this. We can start by noticing that $f(10^{n+1}-1)= 1+10^n+10\times f(10^n-1)$ because when you list all the numbers from 1 to $10^{n+1}$ you get: 1... $10^n-1$, $10^n$,..., 1999...99, 20...00,...$10^{n+1}-1$. from $10^n$ to 1999...99 you can see $10^n+f(n)+1$ the digit '1', and from 20...00 to $10^{n+1}-1$ you get $9\times f(10^n-1)$ the digity '1'. So let's call $u_n=10^n-1$ and $v_n=f(u_n)$.

I can see that $u_9 >v_9$ and $u_{10} < v_{10}$, so the anwswer should be in beetween (or at least smaller than $10^{10}-1$.

  • 1
    $f(10^{n+1})=(n+1)10^n$.2011-06-25
  • 0
    hmm that's true. So $10^{9+1}$ is also a solution. This problem keeps fascinating me, I want to find ALL the solutions to $f(n)=n$ !2011-06-26
  • 0
    How many solutions are there to $f(n) = n!$ ?? $$$$ :)2011-06-27