Digit product

How many positive integers less than 1 , 000 , 000 , 000 1,000,000,000 have the product of their digits equal to 49?


The answer is 120.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

18 solutions

Ben Frankel
Dec 23, 2013

Because this problem involves products, let's find the factorization of 49 49 .

49 = 7 2 49 = 7^2

This implies that the digits of such a positive integer must have exactly two 7 7 s, and the rest of the digits must be 1 1 s. Now we will look at different cases, for different amounts of digits.

When there are 9 digits, we start with a string of nine 1 1 s, and then we pick two of them to replace with 7 7 s. This gives ( 9 2 ) \binom{9}{2} possibilities.

Similarly, for 8 digits, there are ( 8 2 ) \binom{8}{2} possibilities.

Clearly there is a pattern here... the total amount of possibilities is thus:

n = 2 9 ( n 2 ) = 120 \sum\limits_{n=2}^{9} \binom{n}{2} = \boxed{120}

You could have used the hockey-stick identity to simplify computation

William Zhang - 7 years, 5 months ago

Log in to reply

I'm not very experienced in combinatorics, and I did not know of this identity :)

So yes, using the hockey-stick identity this simplifies to one calculation of ( 10 3 ) = 120 \binom{10}{3} = 120

Ben Frankel - 7 years, 5 months ago

Log in to reply

wow amazing ^^

Dan Jodan - 7 years, 5 months ago

what exactly is the hockey-stick identity?

Priyansh Agrawal - 7 years, 5 months ago

Log in to reply

It is this:

i = r n ( i r ) = ( n + 1 r + 1 ) \sum\limits_{i=r}^{n} \binom{i}{r} = \binom{n + 1}{r + 1}

This link provides a proof.

Ben Frankel - 7 years, 5 months ago

Log in to reply

Thank you , Ben !!!!!

Priyansh Agrawal - 7 years, 5 months ago
Dani Chen
Aug 11, 2013

We're trying to find the number of combinations we can make out of two sevens, and n-2 number of ones. Use the combination formula which is: "Number of digits / redundancies".

We can first look at nine digit numbers. It is:

9! / (2!x7!) <-- two sevens and seven ones

Then:

8! / (2!x6!) <-- two sevens and six ones

Keep going until you've done all from nine digits to two digits. Add up the results and you'll get 120 possibilities.

Israel Smith
Dec 23, 2013

For 1-digit numbers = 0 solution, For 2-digit numbers = 1 solution. (77) For 3-digit numbers = (1+2) solutions -> (177,717,771) Combinations with repetition. .... For n-digit numbers = (n²-n)/2 n=9, 1+3+6+10+15+21+28+36 = 120

Tan Li Xuan
Aug 11, 2013

The prime factorization of 49 is 49 = 7 × 7 49=7 \times 7 .So the number must

  • (a) consist of 9 digits or less(from the condition"less than a billion" )

  • (b)consist of only the numbers 7 and 1 (because the only prime factor of 49 is 7)

  • (c) have two of the number 7.

Then we use the formula n ! x ! × y ! × z ! . . . . \frac{n!}{x! \times y! \times z!....} where n n is the number of digits in the number and x , y , z . . . . . x,y,z..... is the number of times one of the digits 0 - 9 appears(the number of distinct digits determines the number of terms in the lower part of the fraction).Here we only have two distinct digits 1 and 7,so we can get n ! 2 ! × ( n 2 ) ! \frac{n!}{2! \times (n-2)!} and then solve it for n = 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 n=2,3,4,5,6,7,8,9 which gives us 1 , 3 , 6 , 10 , 15 , 21 , 28 , 36 1,3,6,10,15,21,28,36 .Then we add the numbers up to get 120 120 .

Moderator note:

Is there a quick way of calculating the sum, without doing the explicit addition? What would our answer be if we're considering all numbers below 1 0 100 10^{100} ?

Using the formula : nCr + nC(r+1)=(n+1)C(r+1)

Adithyan RK - 7 years, 10 months ago

It can be written:

k = 2 k = 9 ( k 2 ) \sum_{k=2} ^ {k=9} {\binom{k}{2}}

Luciano Riosa - 7 years, 10 months ago

Consider that 49 = 7 7 49 = 7\cdot7 . So the possible numbers have from 2 2 up to 9 9 digits. But consider also that if the number has 3 3 digits or more, then the number will be forced to have two 7 7 's, and the other digits will be 1 1 's. So, you have from 2 2 up to 9 9 combinations. This is:

2 ! 2 ! 0 ! + 3 ! 2 ! 1 ! + + 9 ! 2 ! 7 ! = 120 \frac {2!}{2!\cdot0!} + \frac {3!}{2!\cdot1!} + \ldots + \frac {9!}{2!\cdot7!} = \boxed {120} .

Pranav Vashistha
Jan 4, 2014

49 is the product of 7 and 7

all of rest digits are 1

now for 9 digits number we have two 7s and seven 1s

total ways 9! /7!*2!

for 8 digits number we have 8! /6!*2! . . . Similarly for 7,6,5,4,3,2 digits number

we have

Total answer 36+28+21+15+10+6+3+1=120

Chris Catacata
Aug 13, 2013

The numbers satisfying the condition above contain two 7's and 1's.

The total number of number of this digits is computed as:

( 2 2 ) + ( 3 2 ) + ( 4 2 ) + ( 5 2 ) + ( 6 2 ) + ( 7 2 ) + ( 8 2 ) + ( 9 2 ) = 120 \binom {2}{2} + \binom {3}{2} + \binom {4}{2} + \binom {5}{2} + \binom {6}{2} + \binom {7}{2} + \binom {8}{2} + \binom {9}{2} = 120 , representing all the numbers that can be formed using the digits 7 and 1 less than 1 0 9 \text 10^9 .

Naveen Mathew
Jan 12, 2014

There should be two 7s. It should either be the two digit number '77' or a n digit number with all other digits equal to 1. For any n, select 2 places to insert 7s. There are no arrangements => nC2 ways. Answer = 2C2+3C2+4C2+5C2+6C2+7C2+8C2+9C2=120

Anurag Pandey
Jan 8, 2014

the product must be 49 so there is only one factor 7 , to get the product 49 ,in every number there should be only two seven , and other remaining digits can be 1,s as many as we need to get sufficient digits so going step by step in one digit it is not possible in two digit number there is only one number 77 (there should be exactly two seven's )

in three digit there will be three such numbers i.e 177 ,771,717(as there should be one 1's and two 7's) in four digit number there should be two 1's and two 7's so there will be 6 such number (we can use the formula n!/(a!b!)where n is number of digits a is number of 1's and b is number of 7's which will always be 2) now i will make it short in 5 digit 10,in 6digit 15 ,in 7 digit 21 ,in 8 digit 28, in 9 digit 36 we cannot go ahead as if we go it will exceed 1,000,000,000

no we will add those number we got to get all possible ways 1+3+6+10+15+21+28+36 =120 if any doubt you can ask it won't bother me

Giuseppe Zecchini
Dec 29, 2013

First of 49 = 7 2 49=7^2 , so for numbers whose digits are 2 \ge 2 we must have that two digits are 7 and the others are 1. We want find all the permutation of 177,1177,11177,111177,1111177,11111177,111111177. We can see that we are looking for the permutation of words which have two 7 and a variable number of 1 between 0 and 7. Let x x be the number of 1 in our number, so the permutation are ( 2 + x 2 ) \displaystyle {2+x \choose 2} with 0 x 7 0 \le x \le 7 .

The total number of integers is x = 0 7 ( 2 + x 2 ) = ( 10 3 ) = 120 \displaystyle \sum_{x=0}^7{2+x \choose 2 }={10 \choose 3}=120

Eddie The Head
Dec 23, 2013

For the product to be equal to 49 two of the digits must be 7 and the rest must be 1.So we calculate the number of digits possible and we can place the two sevens in any of the digit places.....and the rest of the digits will automatically be equal to 1...So the number of ways this can be done = 2C2 + 3C2 + ........+9C2 = 120

Vikash Kumar
Aug 18, 2013

49=1x7x7; so total no. of 2 digit number from 1,7,7 which product of digits=49 is 2!/2! = 1.

  "     "        3 digit     "          "       1,7,7, "        "              "           is    3!/2! = 3

                  4 digit                          1,1,7,7          "                        "          is    4!/(2!x2!) = 6

                  5  digit                       1,1,1,7,7                                               is    5!/(2!x3!)=10

       on the pattern of this type ,we can write

total no. of positive integers=2!/2! + 3!/2! + 4!/(2!x2!) +5!/(2!x3!) + 6!/(2!x4!) +------+9!/(2!x7!) =120

To let the product of digits be 49,two digits must be 7 and the rest of them be 1(or none).

9 digits

Quantity of numbers: 9 ! 2 ! 7 ! \frac{9!}{2!7!} =36

8 digits

Quantity of numbers: 8 ! 2 ! 6 ! \frac{8!}{2!6!} =28

7 digits

Quantity of numbers: 7 ! 2 ! 5 ! \frac{7!}{2!5!} =21

6 digits

Quantity of numbers: 6 ! 2 ! 4 ! \frac{6!}{2!4!} =15 ......

There is a pattern:the difference of the quantities are 1 fewer.(36-28=8,28-21=7,21-15=6...) Hence,we could know that the next numbers are 10,6,3,1.

Ans=36+28+21+15+10+6+3+1=120

Isak Falk
Aug 13, 2013

49 only has one prime factor; 7, as 49 = 7*7. In essence this means that each number that has 49 as the product of their digits given that it's an integer will consist of two 7's and the rest 1's. As the number will have to be less than a billion, there will be from 1 to 9 spots for these 7's to be placed. As can be seen, the least number of spots needed are 2 as one 7 is not enough. for two spots there will be 1 combination, for three spots 3 and so on, giving the first nine column three entries in pascal's triangle. This sums up to 120.

Dani Natanael
Aug 13, 2013

The factorization of 49 is 49 = 7 x 7 49=7x7 since the possible integers less than 1 , 000 , 000 , 000 1,000,000,000 are consist of 2 digit of 7's and some (or nothing) digits of 1's. The method to find the possible integers is same as we find the possible position of digits 7's in the order of the digits. So, just divide the cases;

(1) Consist of 2 digits, Ex = 77, there's 1 integers.

(2) Consist of 3 digits, Ex = 717, there're ( 3 2 ) = 3 \binom{3}{2}=3 integers

(3) Consist of 4 digits, Ex = 7711, there're ( 4 2 ) = 6 \binom{4}{2}=6 integers

(4) Consist of 5 digits, Ex = 77111, there're ( 5 2 ) = 10 \binom{5}{2}=10 integers

(5) Consist of 6 digits, there're ( 6 2 ) = 15 \binom{6}{2}=15 integers

(6) Consist of 7 digits, there're ( 7 2 ) = 21 \binom{7}{2}=21 integers

(7) Consist of 8 digits, there're ( 8 2 ) = 28 \binom{8}{2}=28 integers

{8} Consist of 9 digits, there're ( 9 2 ) = 36 \binom{9}{2}=36 integers

So, the total possible integers are 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 = 120 1+3+6+10+15+21+28+36=120 integers

CMIIW

Jan J.
Aug 12, 2013

Consider number with i i digits, where 2 i 9 2 \leq i \leq 9 , then the number is of form 1 7 7 1 i digits \underbrace{1 \dots 7 \dots 7 \dots 1}_{i \text{ digits}} . This word can be rearranged in $$\frac{i!}{2! \cdot (i - 2)!}$$ ways, hence there are $$\sum_{i = 2}^{9} \frac{i!}{2! \cdot (i - 2)!} = \boxed{120}$$ such numbers.

we can see that factors of 49 are 7 7 1. so,integer should contain digits(7,7,1) integers can be of 9digits,8digits,....upto 2digits. for 9digit integer, we have 9C2 i.e 36 combination similarly for lesser digit number total no. of possible combination....(9c2+8c2+7c2+6c2+......+2c2)=120

can be made easier for students

santhosh sivan - 7 years, 10 months ago

I know it doesn't hv good readibility but it's easy

vivek kumar yaduka vivek - 7 years, 10 months ago
Caique Ferreira
Dec 24, 2013

Os produtos possíveis, são com dois 7, e complementos de 1. assim : 7 \ times 7 \ times 1 \ times 1 \ times 1 \ times 1 \ times 1 \ times 1 \ times 1. Então faz,a permutação entre eles, de acordo com quantos algarismos terá no número :

\ Frac {9!} {7!2!} +\ Frac {8!} {6!2!}+\ Frac {7!} {5!2!}+\ Frac {6!} {4!2!}+\ Frac {5!} {3!2!}+\ Frac {4!} {2!2!}+\ Frac {3!} {1!2!}+\ Frac {2!} {0!2!}

4 \ times 9 + 4 \ times 7 + 3 \ times 7 + 3 \ times 5 + 2 \ times 5 + 2 \ times 3 + 1 \ times 3 + 1 \ times 1 36 + 28 + 21 + 15 + 10 + 6 + 3 + 1 = 120

Please wrap your text in brackets to ensure proper formatting.

Victor Loh - 7 years, 5 months ago

Write in english please! Escreva em inglês, por favor.

Israel Smith - 7 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...