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

Home > Numbers
Comb(k,2) (Posted on 2018-03-29) Difficulty: 3 of 5
For which k ≥ 3 is k(k-1)/2 (i.e. k choose 2) one more than a power of a prime number?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution with proof | Comment 3 of 4 |
Rewrite k(k-1)/2 - 1 (which must be a power of a prime) as:

(k-2)(k+1)/2

The first or 2nd k-factor is even depending on whether k itself is even.

Suppose k is even, and so k-2 is even and k+1 is odd. Then k/2 - 1 and k + 1 both must be powers of some prime p. k+1 is clearly the larger of the two, so the ratio (k+1)/(k/2 - 1) must be some power of p. It also must be > 1 because k+1 > (k/2 - 1) for all k > 0 and we're given k >= 3. Since the smallest p available is 2, the ratio must be >= 2.

Now for k >= 3, if n > k then (n+1)/(n/2-1) < (k+1)/(k/2-1), and the limit as k goes to infinity is 2. The ratio has a value of 5 when k = 4, 3 when k = 8, and is <3 for k > 8. Since the ratio is also > 2 for all k > 2, the ONLY integral values for the ratio occur for k = 4 and 8. Both of these are indeed solutions, and they are the only ones for even k.


Suppose instead that k is odd. Then k+1 is even and k-2 is odd, and (k+1)/2 and (k-2) must both be powers of the same prime p. They're equal when k = 5, and that's a solution. Otherwise, k-2 is the bigger, so look at the ratio (k-2)/((k+1)/2), which must be a positive power of p. If k > 5 then the ratio is > 1, but it's also < 2 because that's the limit as k goes to infinity. So there are no solutions when k > 5 since there are no primes between 1 and 2. The only other case to consider is k = 3, when the ratio is < 1, and that turns out to be a solution.

So the only odd k solutions are k = 3 and 5, and the only even k solutions are k = 4, 8


  Posted by Paul on 2018-03-29 12:23:53
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 (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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