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$

closed as off-topic by user21820, Jyrki Lahtonen, ArsenBerk, Namaste, stressed out Oct 5 '18 at 22:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Jyrki Lahtonen, ArsenBerk, Namaste, stressed out
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It's unclear what you intend n to represent. $\endgroup$ – Daniel R Hicks Oct 5 '18 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 '18 at 17:09
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$
  • $\begingroup$ I got it, thanks for the great and straightforward explanation! $\endgroup$ – Basma Ashour Oct 5 '18 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$
  • $\begingroup$ Nice explanation, thanks for your help. $\endgroup$ – Basma Ashour Oct 5 '18 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
    $\begingroup$ It's nice to think about it recursively, thank you. $\endgroup$ – Basma Ashour Oct 5 '18 at 8:34

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