1
$\begingroup$

I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10.

What is the correct way to express y in this formula?

$f(x) = 9y + (x/10)$

Where y is the previous result and x is the power of 10 we're checking against.

i.e. $y = 1$ and $x = 100$, or $y = 19$ and $x = 1000$, etc.

For example:

$f(1000) = 9*f(100) + (1000/10)$

and continue recursing until $f(10)$.

I'm a programmer, not a mathematician, so I don't know how to properly express this.

$\endgroup$
5
  • 2
    $\begingroup$ Okay, slow down. My interpretation is that $f(10^n)$ is the number of numbers smaller than $10^n$ which contain the digit $5$, is that right? And $y$ is simply $f(10^{n-1})$? $\endgroup$ – Jack M Jun 4 '14 at 14:50
  • 1
    $\begingroup$ It is very difficult to understand the question. $\endgroup$ – user122283 Jun 4 '14 at 14:50
  • $\begingroup$ Yes. That's correct. I apologize. I'm new here. $\endgroup$ – RubberDuck Jun 4 '14 at 14:51
  • $\begingroup$ Depends on what you mean by previous result. I would guess that what you want is $f(0) = 0$ and $f(n) = 9f(n - 1) + n/10$ for $n > 0$. $\endgroup$ – qaphla Jun 4 '14 at 14:51
  • $\begingroup$ I added (what I hope is) clarification. $\endgroup$ – RubberDuck Jun 4 '14 at 14:56
4
$\begingroup$

What you're saying is that $f(x)$ is the number of positive integers with a $5$ in them that are smaller than $x$. You then claim:

$$f(10^n) = 9f(10^{n-1}) + \frac {10^n} {10} = 9f(10^{n-1}) + 10^{n-1}$$

That technically answers your question "what is the correct way to express $y$?", but I'm not sure that's what you meant to ask.

Your formula is indeed correct, incidentally, and can be easily proven by the following argument. $f(10^n)$ is just the number of $n-1$-digit numbers with a $5$ in them. Take any $n-2$ digit number with a $5$ in it, and you can use it to get $9$ $n-1$ digit numbers with a $5$ in them by simply putting a $0$, $1$, $2$, $3$, $4$, $6$, $7$, $8$ or a $9$ in front of it. So that gives us $9f(10^{n-1})$ possibilities, but we haven't covered $n-1$ digit numbers that start with a $5$. There are $10^{n-1}$ of those, and they all obviously have a $5$ in them, so in total we have $f(10^n)=9f(10^{n-1})+10^{n-1}$, as claimed.

The recurrence relation can in fact be solved for an explicit formula for $f$. To abbreviate, let $a_n=f(10^n)$, so:

$$a_0=0$$ $$a_n=9a_{n-1}+10^{n-1}$$

Let $\delta_n=a_n-9a_{n-1}=10^{n-1}$ for $n\geq1$. We can get $a_n$ from the $\delta_i$s, for example:

$$a_3=\delta_3+9a_2=\delta_3+9(\delta_2+9a_1)=\delta_3+9\delta_2+9^2a_1=\delta_3+9\delta_2+9^2\delta_1$$

The pattern is obvious, and we can prove by induction that $a_n=\sum^n_{i=1}\delta_i9^{n-i}=\sum^n_{i=1}10^{i-1}9^{n-i}$ (remember that $\delta_i=10^{i-1}$). Now it's just algebra:

$$a_n=\sum^n_{i=1}10^{i-1}9^{n-i}=\frac{9^n}{10}\sum^n_{i=1}10^{i}9^{-i}=\frac{9^n}{10}\sum^n_{i=1}\left(\frac{10}{9}\right)^i=\frac{9^n}{10}\left(\frac{(\frac{10}{9})^{n+1}-1}{\frac{10}{9}-1} - 1\right)$$

In the last step I applied the formula for a geometric sum.

You can simplify this a little bit with more algebra:

$$a_n=\frac {10^{n+1} - 9^{n+1} - 9^n} {10}=10^n - \frac {9^{n+1}+9^n} {10}=10^n - \frac {9^n(9+1)} {10}=10^n - 9^n$$

(For the sake of humility, I'll just note that I had to consult the OEIS before spotting that very last simplification) This is a better formula if we're talking about computers, since it doesn't require floating points. Whether it's faster than your recursive formula I don't know, but it's interesting nonetheless.

$\endgroup$
8
  • $\begingroup$ I have no idea what "non-homogeneous linear recurrence relation means", but I think you answered my question. Are you concerned that I have my algorithm wrong? $\endgroup$ – RubberDuck Jun 4 '14 at 15:07
  • $\begingroup$ @ckuhn203 It definitely seems to be correct based on my tests, I just can't think of a proof off the top of my head. Also, I just realized I may have made a mistake, the formula might not be technically linear and I'm not sure it can be solved. $\endgroup$ – Jack M Jun 4 '14 at 15:07
  • $\begingroup$ Sorry. I posted that before your edit. It does seem to be. I was able to check with a brute force program out to 10^5 before I had to find a more elegant solution. I had to do a lot of hand work to figure it out. I wouldn't know how to begin proving it. $\endgroup$ – RubberDuck Jun 4 '14 at 15:09
  • $\begingroup$ Thank you @JackM. You're a gentleman and a scholar. $\endgroup$ – RubberDuck Jun 4 '14 at 15:20
  • $\begingroup$ @ckuhn203 Turns out you can in fact solve the recurrence and get a formula for $f$. I edited the calculation into the answer. You may or may not be able to follow it depending on how much math you've studied, but I'm sure you'll at least be able to understand the end result, if you're interested. $\endgroup$ – Jack M Jun 4 '14 at 15:53
3
$\begingroup$

Here's a simple way to arrive at @JackM's closed-form expression:

  • $10^n$ = the count of all numbers up to $n$ digits
  • $9^n$ = the count of all numbers up to $n$ digits that don't contain 5 anywhere
$\endgroup$
2
  • $\begingroup$ And that is also wrong... $0002353$ is not a (properly written) number. $\endgroup$ – vonbrand Jun 18 '14 at 15:54
  • 1
    $\begingroup$ @vonbrand Why should it matter if there are leading zeros? The question asks, up to n digits. $\endgroup$ – 200_success Jun 18 '14 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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