Do Two Primes Divide All Binomial Coefficients for Any n?

[haruspex]

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!

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.

 

[Joffan]

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!

Yes indeed. For example, taking n=210, p=7 and q=103 (from 206), C(210,105) is not divisible by either p or q.

If you can reach a "pure" prime or prime power, though, you're safe , as is the case for 520260.

 

[PeroK]

If there is a countereaxmple using the "simple" method of looking for the largest prime factors, then that counterexample will be valid. This is because each pair of factors will cancel together before their product. So, looking at fg is a worst case. Also, f and g both have to cancel before (n+1)/2, as the binomials repeat for k after that.

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.

There is a relationship between the required gaps in the primes and the size of prime factors. E.g.

If all prime factors are less than 10, then the maximum n is 8.9.5.7 = 2520. So, you need a gap of at least 10 numbers without primes.

If all prime factors are less than 20, then the maximum n is about 250 million. So, you need a gap of about 20. But, with a lot more choice of n. There are some gaps of about 250 at this range.

It seems plausible, therefore, that there is a counterexample. But hard to find.

 

[Joffan]

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.

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.

The cases where I needed to go to the second factor of the initial number seemed to be getting less frequent as n increased.

Another interesting were a large number of cases where two relatively small factors did the job. For the most extreme example, for 18027009, 29 and 2 (for 512, from 18027008) covered divisibility of all coefficients. I'd love if someone else checked that...

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