login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0

%I #29 Jan 24 2021 18:33:47

%S 31416,46800,195624,5504490,7458780,9968112,12387600,105666600,

%T 115690848,130559352,146187444,225613050,275172996,282429840,

%U 300688752,539509620,653426796,696595536,784474592,798772578,815224800,851716320

%N 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.

%C 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.

%C 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.

%C 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.)

%H John Shareshian and Russ Woodroofe, <a href="http://arxiv.org/abs/1505.05143">Divisibility of binomial coefficients and generation of alternating groups</a>, arXiv:1505.05143 [math.CO], 2015.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Kummer%27s_theorem">Kummer's theorem</a>

%e 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.

%e 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.

%o (GAP) See Shareshian & Woodroofe link.

%K nonn

%O 1,1

%A _Russ Woodroofe_, Jun 04 2015

%E Typo in description fixed by _Russ Woodroofe_, Aug 09 2015

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:16 EDT 2024. Contains 371264 sequences. (Running on oeis4.)