What is the smallest value of n for which the product of

Question

What is the smallest value of n for which the product of 1*2*3*4*....n is divisible by  2^{27} ?

This is my own question, not a question of GMAT authors. Not sure how likely this type of question is to be on the real thing, but the principles behind the answer are rather interesting. Let me know if you want me to clarify something about the question.

x2suresh · Answer

Is that 2^27 or 2^2 * 7??

scthakur · Answer

Not sure if I understood the question correctly.

If you refer to 2^(27), then I will get 2s from even numbers of 1*2*3*4*....till I reach 27 or more 2s. The first time I get 27 (or more) 2s is when n is 32.

(2^1)*(2^2)*(2^1)*(2^3)*(2^1)*(2^2)*(2^1)*(2^4)*(2^1)*(2^2)*(2^1)*(2^3)*(2^1)*(2^2)

However, if you meant (2^2)*7, then obviously, n will be 7.

jallenmorris · Answer

2^{27}  or 2^(27) - sorry about that.

durgesh79 · Answer

count 2s and stop when total > 27
number - 2s - total 
2 - 1 - 1
4 - 2 - 3
6 - 1 - 4
8 - 3 - 7
10 - 1 - 8
12 - 2 - 10
14 - 1 - 11
16 - 4 - 15
18 - 1 - 16
20 - 2 - 18
22 - 1 - 19
24 - 3 - 22
26 - 1 - 23
28 - 2 - 24
30 - 1 - 25
32 - 5 - 30

n = 32

x2suresh · Answer

I assume it is 2^27

1*2*3*4*....n . = 2^1* 2^2 * 2^3 ... 1*3*5*9..
 = 2^ (1+2+3....x)...

(1+2+3....x)... we have to find x such that sum is the smallest possible value greater than > 27

x(x+1)/2 >27 when x=7 x(x+1)/2 = 28.

so x has to be 7
max term is 2^7= 128

n=128

oopss!! I didnt consider.. 6 * 12*..10*.14*...

jallenmorris · Answer

I've created a spreadsheet to try this out thinking that it would be simple to count the number of 2's and that is the answer. Whatever n! has the right number of 2s, then that's your answer, but Excel is telling me otherwise and I'm not sure why.

Excel is telling me there are 27-2's in 23!
---------25852016738885000000000.0 <- This is 23! I then divide by 2. the 1---is the count of 2's
1--------12926008369442500000000.0
2--------6463004184721240000000.0
3--------3231502092360620000000.0
4--------1615751046180310000000.0
5--------807875523090156000000.0
6--------403937761545078000000.0
7--------201968880772539000000.0
8--------100984440386269000000.0
9--------50492220193134700000.0
10-------25246110096567400000.0
11-------12623055048283700000.0
12-------6311527524141840000.0
13-------3155763762070920000.0
14-------1577881881035460000.0
15-------788940940517730000.0
16-------394470470258865000.0
17-------197235235129433000.0
18-------98617617564716300.0
19-------49308808782358100.0
20-------24654404391179100.0
21-------12327202195589500.0
22-------6163601097794770.0
23-------3081800548897380.0
24-------1540900274448690.0
25-------770450137224346.0
26-------385225068612173.0
27-------192612534306086.0
28-------96306267153043.2 <- Decimal. No longer another 2?

Nerdboy · Answer

It should be 32.

32! has 32/2 numbers divisible by 2, 32/4 numbers divisible by 4, ... 32/16 divisible by 16. So, 32/2=16 means we have 16 even numbers; 32/4=8 means in addition to those 16 even numbers we have 8 more twos and so on. You can add those for a total of 30 2s. Or am I doing something wrong?

GMAT TIGER · Answer

its trail & error

lets try at 30!:
30/2 = 15
30/4=7
30/8=3
30/16=1
30/32=0
total number of 2's in 30! = 26. we need 1 more 2. so definitely it is 32!.

jallenmorris · Answer

I know you're all saying it should be 32! or something way higher than I am, but:

What is the value of  2^{27} ? 134217728

What is the value of 32!? 263130836933694000000000000000000000

Yes, 32! is evenly divisible by  2^{27} , but it's not the smallest number that is divisible by  2^{27} .

23! = 25,852,016,738,885,000,000,000

1) 25852016738885000000000<--Start and divide by 2 = the next line
2)12926008369442500000000 <--again divide by 2
3)6463004184721240000000 <--again divide by 2 and down the line
4)3231502092360620000000
5)1615751046180310000000
6)807875523090156000000
7)403937761545078000000
8)201968880772539000000
9)100984440386269000000
10) 50492220193134700000
11)25246110096567400000
12)12623055048283700000
13)6311527524141840000
14)3155763762070920000
15)1577881881035460000
16)788940940517730000
17)394470470258865000
18)197235235129433000
19)98617617564716300
20)49308808782358100
21)24654404391179100
22)12327202195589500
23)6163601097794770
24)3081800548897380
25)1540900274448690
26)770450137224346
27)385225068612173

This is from Excel and I'm kind of thinking it's messed up because when I divide 385225068612173 by 2, it gives me 192612534306086
Which of course isn't correct if the units digit is 3!

Nerdboy · Answer

I also tried with Excel and arrived at the same result as you... Could it be that Excel is actually not giving an integer value and hides some digit located at the 10,000,000 mark after the decimal point?

jallenmorris · Answer

It's possible, but if we apply the rules we know about multiplication of odd/even numbers, the process we're using should be exactly right.

My only other question with this is once we've pulled out all the 2's in say 23!, we should be left with only odd numbers.

An odd*odd = an odd product.

23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2
Prime factorization of 23!
23*(2*11)*(3*7)*(2*2*5)*19*(2*3*3)*17*(2*2*2*2)*(3*5)*(2*7)*13*(2*2*3)*11*(2*5)*(3*3)*(2*2*2)*7*(2*3)*5*(2*2)*3*2

There are 19-2's in 23!

So, the largest power of 2 divisible into 23! would be 2^19, right?

The odd primes remaining are 23*11*3*7*5*19*3*3*17*3*5*7*13*3*11*5*3*3*7*3*5*3

Someone correct me if I'm wrong:

The only way would could get any additional 2's out of the product of the odd primes is if we multiplied some of them and then multiplied that product by 2 (in order to get an even number because odd*odd = odd) and then that even number would have to be divisible by at least 4 or else we would not have "discovered" any additional 2's.

This just isn't going to happen. Sometime has to be wrong with how excel processes the huge numbers. The method of prime factorization and counting 2's has to be the best method.

GMAT TIGER · Answer

exactly. excel doesnot give the exact result for values beyond certain digit.

What is the smallest value of n for which the product of

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards