All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Two Power Divides Product (Posted on 2011-12-05) Difficulty: 2 of 5
Find n where 2n is the largest power of 2 that divides the product 2011*2012*2013*.....*4022

No Solution Yet Submitted by K Sengupta    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution analytic solution and computer solution | Comment 2 of 8 |

There are 2012 numbers in the range 2011 through 4022 and half are even, giving us a start of 1006 factors of 2.

2012 is divisible by 4, so 503 are multiples of 4, adding 503 more factors equal to 2, making 1509 so far.

2011 is 3 mod 8 and 4022 is 6 mod 8, so that of the 2012 numbers in the given range, [2012/8] = 251 are divisible by 8, bringing the total to 1760.

2011 is 11 mod 16 and 4022 is 6 mod 16, so that of the 2012 numbers in the given range, ceil(2012/16) = 126 are divisible by 16, bringing the total to 1886.

2011 is 27 mod 32 and 4022 is 22 mod 32, so that of the 2012 numbers in the given range, ceil(2012/32) = 63 are divisible by 32, bringing the total to 1949.

2011 is 27 mod 64 and 4022 is 54 mod 64, so that of the 2012 numbers in the given range, [2012/64] = 31 are divisible by 64, bringing the total to 1980.

2011 is 91 mod 128 and 4022 is 54 mod 128, so that of the 2012 numbers in the given range, ceil(2012/128) = 16 are divisible by 128, bringing the total to 1996.

2011 is 219 mod 256 and 4022 is 182 mod 256, so that of the 2012 numbers in the given range, ceil(2012/256) = 8 are divisible by 256, bringing the total to 2004.

2011 is 475 mod  512 and 4022 is 438 mod  512, so that of the 2012 numbers in the given range, ceil(2012/512) = 4 are divisible by 512, bringing the total to 2008.

2011 is 987 mod 1024 and 4022 is 950 mod 1024, so that of the 2012 numbers in the given range, ceil(2012/1024) = 2 are divisible by 256, bringing the total to 2010.

2048 is within the range, bringing the final total to 2011.

Computer verification:

FOR n = 2011 TO 4022
  nu = n
  WHILE nu MOD 2 = 0
    ct = ct + 1
    nu = nu \ 2
  WEND
NEXT
PRINT ct

which finds

2011


  Posted by Charlie on 2011-12-05 13:33:44
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information