A258577 Numbers n with greatest prime power divisor p^a, such that gcd{binomial(n,k) : 1 <= k <= n-1, binomial(n,k) is not divisible by p} = 1.

31416, 46800, 195624, 5504490, 7458780, 9968112, 12387600, 105666600, 115690848, 130559352, 146187444, 225613050, 275172996, 282429840, 300688752, 539509620, 653426796, 696595536, 784474592, 798772578, 815224800, 851716320

Offset

1,1

Comments

For an integer m, it is frequently the case that one can find a pair of primes p, r such that every nontrivial entry binomial(m,k) in the m-th row of Pascal's triangle is divisible by either p or r (or both). Indeed, we have shown by computation that one can find such a pair of primes for every m < 1 billion. We also have suggestive asymptotic density results.

Since m = binomial(m,1), it is obvious that, without loss of generality, p must be a divisor of m. A certain sieve result (see referenced arXiv paper) suggests that taking p to be the prime associated with the largest prime power divisor of m might be a good choice. Surprisingly, even when the sieve does not apply, this choice of p often still works. The numbers in the above sequence are the values out to m = 1 billion where this choice of p fails. The GAP program to generate these took about 2 weeks to run on a 2.9 GHz MacBook Pro from 2012.

Except when m is a prime power, the problem stated above is equivalent to the problem of whether there are a pair of primes p, r such that <P,R> = A_m for any Sylow p-subgroup P and Sylow r-subgroup R of A_m. (Proved in the referenced arXiv paper.)

Links

Table of n, a(n) for n=1..22.

John Shareshian and Russ Woodroofe, Divisibility of binomial coefficients and generation of alternating groups, arXiv:1505.05143 [math.CO], 2015.

Wikipedia, Kummer's theorem

Example

For m = a(1) = 31416 = 2^3*3*7*11*17, the largest prime power divisor is 17. By Kummer's Theorem (see links), binomial coefficients binomial(m,k) are divisible by 17 except possibly when 17 divides k. However, the gcd of such coefficients is 1.
While there is no prime r such that 17 or r divides every nontrivial binomial(m,k), it is nonetheless true that every nontrivial binomial coefficient is divisible by one of the primes 2, 7853.

Prog

(GAP) See Shareshian & Woodroofe link.

Crossrefs

Sequence in context: A351852 A274045 A277171 * A303531 A251006 A113846

Adjacent sequences: A258574 A258575 A258576 * A258578 A258579 A258580

Keyword

nonn

Author

Russ Woodroofe, Jun 04 2015

Extensions

Typo in description fixed by Russ Woodroofe, Aug 09 2015

Status

approved