

A258577


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


0



31416, 46800, 195624, 5504490, 7458780, 9968112, 12387600, 105666600, 115690848, 130559352, 146187444, 225613050, 275172996, 282429840, 300688752, 539509620, 653426796, 696595536, 784474592, 798772578, 815224800, 851716320
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 mth 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 wlog 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 psubgroup P and Sylow rsubgroup 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: A177217 A274045 A277171 * A251006 A113846 A234205
Adjacent sequences: A258574 A258575 A258576 * A258578 A258579 A258580


KEYWORD

nonn


AUTHOR

Russ Woodroofe, Jun 04 2015


EXTENSIONS

Fixed typo in description by Russ Woodroofe, Aug 09 2015


STATUS

approved



