Stack Exchange network consists of 180 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
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.
$\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$
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:
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:
By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.
n
to represent. $\endgroup$