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

Home > Just Math
Factorial Quotient (Posted on 2011-11-19) Difficulty: 3 of 5
Find a positive integer p such that: (p+1)(p+2)....(p+500)/500! is an integer with no prime factors less than 500.

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

Comments: ( Back to comment list | You must be logged in to post comments.)
solution | Comment 2 of 4 |
I first noticed that the divisors of (p+1) to (p+500) can't contain any power of 2 higher than those present in the divisors of 1 to 500. Since 2^9 is the first power of 2 greater than 500, p mod 512 < 12, otherwise one of the 500 values in the numerator will be a multiple of 512, and the prime factors will have more 2's on top than on bottom.

Likewise, for 3, our first power not present in 1 to 500 is 3^6 = 729. If we continue on in this manner, using (p mod x^k = 0), for all primes x, under 500, and k equal to the first power of x greater than 500, we arrive at:

p = 2^9 * 3^6 * 5^4 * 7^4 * 11^3 * 13^3 * 17^3 * 19^3 * 23^2 * ... * 499^2 =
91437123477078912482945878919818614446532982092966112
98598203702959733093184392976646789414501641695754334
91165107683102061044929944424456729471272041645917843
57555124591545550921295288359185770833608053407629499
00428923273468427530213361727711222442978249783069383
70979132203308537416888543221723107701793761798042239
49839776972405284898497419609419360525294877874473901
29807557513509094617238289082443341089051901715520000

This guarantees* that (p+1) to (p+500) will have the same prime factorization (for primes under 500) as that of 500!, and a quick run through, factoring all numbers for prime factors under 500 confirms that all 2's, 3's, ..., and 499's cancel, and no prime factors under 500 exist in the quotient.

*Note: The reason I say this is guaranteed is as follows. As p is a multiple of 512, then p mod 2 = 0, p mod 4 = 0, ..., p mod 256 = 0. These are all identical to that of zero mod 2, zero mod 4, ..., zero mod 256. Thus, all prime factors of 2 in (p+1) to (p+500) will be distributed identically to those in 1 to 500. Likewise, for the prime factors for 3's, p mod 3 = 0, p mod 9 = 0, ..., p mod 243 = 0. In this manner, we are able to essentially "reset" our position in the number line, to 0, and create a perfect copy of the prime factorization for those primes under 500.

Edited on November 20, 2011, 4:40 pm
  Posted by Justin on 2011-11-20 16:37:48

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 (9)
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