1
$\begingroup$

I wanna know how many numbers $n$ are there which only contain digits $4$ and $7$ in them, where $1 ≤ n ≤ 10^9$.

Ex: $4, 7, 44, 47, 74, 77, ...$

I am trying to find a general equation to compute the numbers, given how many digits, which is $2$ in this case, and the range, which is $1 ≤ n ≤ 10^9$ in this case.

$\endgroup$
2
  • $\begingroup$ It's unclear what you intend n to represent. $\endgroup$ Oct 5, 2018 at 14:31
  • 1
    $\begingroup$ I really recommend that you try to solve this entirely on you own. This is a excellent introduction to problem solving and is simple enough that anyone no matter how limitted their math skill should be able to figure it out. As a starter try solving for $1 \le n \le 10^k$ were $k = 1,2,3$ first. You will really feel good about yourself when you figure it out on your own. So I'm not giving any hint. Good luck and enjoy. $\endgroup$
    – fleablood
    Oct 5, 2018 at 17:09

3 Answers 3

10
$\begingroup$

Well, how do you create a number of $i$ digits where all the digits are $4$ and $7$? For each of the $i$ digits you have to choose if it will be $4$ or $7$, so for each digit you have $2$ options. Hence the number of such numbers is $2^i$. Now, how is that related to your problem? You are interested in finding how many numbers are there that contain only digits $4$ and $7$ when the number of digits is between $1$ and $9$. Well, there are $2^1$ numbers with $1$ digit, $2^2$ with $2$ digits and so on. So the final answer is:

$\sum_{k=1}^9 2^k=2(2^9-1)$

I used the formula for geometric sum.

$\endgroup$
1
  • $\begingroup$ I got it, thanks for the great and straightforward explanation! $\endgroup$ Oct 5, 2018 at 8:25
3
$\begingroup$

There are $2$ with length $1$, $2^2$ with length $2$, $2^3$ with length $3$, et cetera.

That observation leads to a total of:$$2+2^2+2^3+\cdots+2^9=2^{10}-2$$

The last equation on base of: $$(2-1)(2+2^2+2^3+\cdots+2^9)=(2^2+2^3+\cdots+2^{10})-(2+2^2+2^3+\cdots+2^9)=2^{10}-2$$

$\endgroup$
1
  • $\begingroup$ Nice explanation, thanks for your help. $\endgroup$ Oct 5, 2018 at 8:34
2
$\begingroup$

One can also derive a recurrence formula for such problem.

  • Notice that the number of these numbers less than $100$ is $S=\{\{4,7\},\{44,47,74,77\}\}$ Notice also that the set $S$ is divided into two subsets, call them $s_1,s_2$

  • For a bound equal to $1000$, take $s_2$ and augment $4,7$ to each number, add them to the set $S$ call it $S_{new} = \{\{4,7\},\{44,47,74,77\},\{444,447,474,477,744,747,774,777\}\}$ The number of elements of $S_{new}$ is $2*|s_2|+6=14$. Or more generally: $$|S_{new}| = 2*(|S|-|S_{old}|)+|S|, S_{old} = s_1.$$

  • For numbers below $10^4$, take the last subset and augment 7,4 to it and add to the set. The total number would be: $2*8+14 = 30$. Or $$|S_{new}| = 2*(|S|-|S_{old}|)+|S|, S_{old} = s_1+s_2$$ and so on.

I hope that the recurrence is clear now:

$$f(n) = 2[f(n-1)-f(n-2)]+f(n-1)$$ Or equivalently:

$$f(n) = 3f(n-1)-2f(n-2)$$

Solving this recurrence by Wolfram Alpha check here, the answer is:

$$f(n) = 2(2^n-1)$$

Which is identical to the other answers.

$\endgroup$
1
  • 1
    $\begingroup$ It's nice to think about it recursively, thank you. $\endgroup$ Oct 5, 2018 at 8:34

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