The discussion centers on the proposition that for each integer n ≥ 2, there exist two distinct primes p and q that divide every binomial coefficient ##\binom{n}{k}## for 1 ≤ k ≤ n-1. Initial examples demonstrate that for n = 6, primes 2 and 3 divide all relevant binomial coefficients, while for n = 3, prime 3 suffices alone. The consensus is that the original statement should be revised to assert that at most two distinct primes can divide each ##\binom{n}{k}##. The discussion reveals complexities in proving this proposition, particularly when n is a prime or prime power, and suggests that counterexamples may exist when n and n-1 are products of distinct primes.
PREREQUISITESMathematicians, number theorists, and students interested in combinatorial mathematics and the properties of binomial coefficients, particularly those exploring divisibility by primes.
Yes, I worried I was missing something there, but didn't see it. So there's a penalty as you step down down the sequence from n. If the second factor, g, is from n-1 then the terms it won't divide occur in pairs, k=g, k=g+1; if from n-2 then they occur in triples, etc. Consequently, it might not be best to take the largest prime power factor from n that you can. Ouch.PeroK said:Actually, this is not quite right. If the primes are picked from different integers, then their factorisation sequences are not in sync. E.g. if p = 5 is a factor of n and p = 7 is a factor of n-1, then they both cancel when k = 15 (not 35). And p = 25 and q = 49 would cancel at k = 50.
Very tricky!
PeroK said:Actually, this is not quite right. If the primes are picked from different integers, then their factorisation sequences are not in sync. E.g. if p = 5 is a factor of n and p = 7 is a factor of n-1, then they both cancel when k = 15 (not 35). And p = 25 and q = 49 would cancel at k = 50.
Very tricky!
I did more-or-less this, out to 20 million, on Sunday. For cases where gap from the last prime-power is greater than the largest prime-power factor of a number (2378 cases), I looked at the preceding numbers and checked directly whether their largest prime-power factor gave the divisibility coverage required. Usually one of them did; in a few cases {31416, 46800, 195624, 2999568, 5504490, 7458780, 9968112, 12387600} none did, but then taking the second-largest prime-power factor of the original number always turned up a coverage pair.PeroK said:A better algorithm would check each pair more precisely if their product is greater than (n+1)/2, as they may cancel before that. Joffan is correct, though, that you have to avoid primes. If you started with a list of primes, you could look for relatively large gaps.
Function NFacMDiv(ByVal NFac As Long, MDiv As Long) As Long
' return power of prime MDiv in nFac!
NFacMDiv = 0
Do While NFac > 0
NFac = Int(NFac / MDiv)
NFacMDiv = NFacMDiv + NFac
Loop
End Function
Function nCrMDiv(ByVal FromN As Long, ChooseK As Long, MDiv As Long) As Long
' return power of prime MDiv in C(FromN, ChooseK)
If ChooseK <= FromN Then
nCrMDiv = NFacMDiv(FromN, MDiv) - NFacMDiv(ChooseK, MDiv) - NFacMDiv(FromN - ChooseK, MDiv)
Else
nCrMDiv = -1
End If
End Function