[seqfan] Comment on A151750 [erratum]

[peter.luschny]

David Wilson wrote:

DW> Theorem: For prime p
DW>
DW>    p does not divide choose(2n, n) <=> all p-ary digits of n are < p/2.
DW>
DW> Proof: The exponent of prime p in n! is given by
DW>
DW>    [1] e_p(n) = (n - s_p(n))/(p -1)
DW>
DW> where s_p(n) is the sum of the p-ary digits of n (well known to those who
DW> well know it).
DW>
DW> So p does not divide choose(2n, n) = (2n)! / (n!)^2 precisely when
DW>
DW>    e_p(2n) - 2e_p(n) = 0
DW>
DW> Together with [1], this implies
DW>
DW>    s_p(2n) = 2 s_p(n)
DW>
DW> But the sum of p-ary digits in 2n is twice the sum of the p-ary digits in n
DW> precisely when there is no carry in the sum n+n, that is to say,
every p-ary
DW> digit of n is < p/2, QED.

Thank you David. When reading your proof Legendre's theorem and
Kummer's theorem comes to my mind. I think Andrew Granville
has given a nice exposition on that somewhere on the web.
But why restrict oneself to the case choose(2n,n)? I will
recast the theorem in terms of the swinging factorial n$.

Theorem: For prime p

   p does not divide n$ <=> exists k such [n/p^k] is odd.

Proof: The exponent of prime p in n$ is given by

   e_p(n) = sum{k>0} [n/p^k] mod 2 .

QED.

The problems in my original posting are somewhat harder.
Ron Graham for example offers 1000$ for one of them.

Cheers Peter

P.S. The Maple procedure below computes the set of
primes which do not divide n$ by the above theorem.

PrimeDividesSwingTest := proc(n)
local sw,p,q,div,P,t,s;
sw := n!/iquo(n,2)!^2; div := {};
P := select(isprime,[$1..n]);
for p in P do q := p; s := -1;
while q <= n do t := irem(iquo(n,q),2) = 1;
if t then s:=1; break fi; q := q*p od;
div := div union {s*p} od;
print(div minus numtheory[factorset](sw)) end:

seq(PrimeDividesSwingTest(n),n=70..77);

{-5, -11, -17, -29, -31}
{-5, -11, -17, -29, -31}
{-3, -5, -11, -17, -29, -31}
{-3, -5, -11, -17, -29, -31}
{-3, -5, -11, -17, -29, -31, -37}
{-11, -17, -29, -31, -37}
{-11, -17, -19, -29, -31, -37}
{-17, -19, -29, -31, -37}