The discussion revolves around the question of whether there exist two primes \( p \) and \( q \) such that for each \( n \geq 2 \), these primes divide all binomial coefficients \( \binom{n}{k} \) for \( 1 \leq k \leq n-1 \). The original poster provides examples and seeks to prove this statement, exploring the implications of prime factors in binomial coefficients.
The discussion is ongoing, with various interpretations being explored. Some participants have raised concerns about the clarity of the problem statement and the conditions under which the primes divide the binomial coefficients. There is no explicit consensus, but several lines of reasoning and counterexamples are being considered.
Participants note that the problem may depend on the nature of \( n \), particularly when \( n \) is a prime or a prime power. There are also discussions about the implications of shared prime factors between \( n \) and \( n-1 \), as well as the potential for counterexamples involving products of distinct 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