How many numbers are there which only contain digits $4$ and $7$ in them?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.