User:Peter Luschny/PrimeFactorsSwingingFactorial

On the prime factors of
the swinging factorial.

KEYWORDS: swinging factorial, central binomial coefficient, conjecture of Erdös, Graham et al.

Concerned with sequences:  A000984, A056040, A005836, A129508, A030979, A151750, A055246, A196747, A196748, A196749, A196750.

A conjecture of Erdös, Graham et al.

Here we are concerned with a generalization of some simple divisibility properties of the central binomial coefficient. Or better, we consider a more natural formulation of some observations and conjectures which have as starting point the paper by P. Erdös, R. L. Graham, I. Z. Russa and E. G. Straus, On the prime factors of C(2n,n), Math. Comp. 29 (1975), 83-92.

We will use the following notation:

$n\perp [p_{1},\ldots ,p_{k}]\ \Longleftrightarrow \ n\perp p_{1}\wedge \cdots \wedge \ n\perp p_{k}$

This means that n is relatively prime to every p_i in the list. It generalizes Knuth's notation for gcd(n,k) = 1.

Concerned with sequences

The swinging factorial $n\wr$ is sequence A056040 and the central binomial ${\binom {2n}{n}}$ is sequence A000984.

• A005836  ${\binom {2n}{n}}\perp [3]$
• A129508   ${\binom {2n}{n}}\perp [3,5]$
• A030979  ${\binom {2n}{n}}\perp [3,5,7]$
• A151750   ${\binom {2n}{n}}\perp [3,5,7,11]$
• A000000   ${\binom {2n}{n}}\perp [3,5,7,11,13]$

• A196747   $n\wr \perp [3]$
• A196748   $n\wr \perp [3,5]$
• A196749   $n\wr \perp [3,5,7]$
• A196750   $n\wr \perp [3,5,7,11]$
• A000000   $n\wr \perp [3,5,7,11,13]$

A196747: seq(search(i,[3],1),i=0..200);
0, 1, 2, 6, 7, 8, 18, 19, 20, 24, 25, 26, 54, 55, 56,
60, 61, 62, 72, 73, 74, 78, 79, 80, 162, 163, 164, 168,
169, 170, 180, 181, 182, 186, 187, 188, 

A005836: seq(search(i,[3],2),i=0..250);
0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39,
40, 81, 82, 84, 85, 90, 91, 93, 94, 108, 109, 111, 112,
117, 118, 120, 121, 243, 244, 246, 247

A196748: seq(search(i,[3,5],1),i=0..6500);
0, 1, 2, 20, 24, 54, 60, 61, 62, 72, 73, 74, 504, 510,
511, 512, 560, 564, 1512, 1513, 1514, 1520, 1620, 1621,
1622, 6320, 6324, 6372, 6373, 6374, 6500

A129508: seq(search(i,[3,5],2),i=0..4000);
0, 1, 10, 12, 27, 30, 31, 36, 37, 252, 255, 256, 280,
282, 756, 757, 760, 810, 811, 3160, 3162, 3186, 3187,
3250, 3252, 3276, 3277, 3280

A196749: seq(search(i,[3,5,7],1),i=0..120000000);
0, 1, 2, 20, 1512, 1513, 1514, 6320, 6372, 6373, 6374,
6500, 15120, 15121, 15122, 15302, 40014, 119096754,
119096802

A030979: seq(search(i,[3,5,7],2),i=0..60000000);
0, 1, 10, 756, 757, 3160, 3186, 3187, 3250, 7560,7561,
7651, 20007, 59548377, 59548401

A196750: seq(search(i,[3,5,7,11],1),i=0..100000);
0, 1, 2, 6320

A151750: seq(search(i,[3,5,7,11],2),i=0..100000);
0, 1, 3160

A000000: seq(search(i,[3,5,7,11,13],1),i=0..100000);
0, 1, 2

A000000: seq(search(i,[3,5,7,11,13],2),i=0..100000);
0, 1

Basically the conjectures are: A030979 and A196749 are infinite sequences whereas A151750 and A196750 are finite sequences. Citing from the comment to A030979:

"Ronald L. Graham offers $1000 to the first person who can settle the question of whether this sequence is finite or infinite. He remarks that heuristic arguments show that it should be infinite, but finite if it is required that C(2n,n) is prime to 3, 5, 7 and 11, with n = 3160 probably the last n which has this property."

With regard to A196750 this means that 6320 might be the last element of this sequence.

Computing the sequences

search := proc(n,L,f) 
local m, i, r; m := f*n;
for i in L do 
   r := SwingExp(i,m); 
   if r <> 0 then RETURN(NULL) fi 
od;
n end:

Thus we see that the binomial formulation is just a particular case of the swinging formulation. The binomial formulation only introduces factor of 2, which is irrelevant with regard to divisibility properties under consideration. It remains to give the function SwingExp(m,n) to compute all 10 sequences efficiently.

SwingExp := proc(m,n) 
local p, q; p := m;
do q := iquo(n,p);
   if (q mod 2) = 1 then RETURN(1) fi;
   if q = 0 then RETURN(0) fi;
   p := p * m;
od end:

We remark that an implementation in C needs 10 seconds to compute the above list for A196749 and 5 seconds for A030979 on a PC vintage 2004. For A030979 terms up 3^41 were computed by Max Alekseyev in 2008. It is a pitty that there is no indication which method Alekseyev used. I think if such particulars were included in OEIS this would stimulate the numerical exploration of sequences like the above.

Discoveries

Now, what is the relation between the above binomial-based sequences and the swing-based sequences? If B is a binomial-based sequence then 2B is a subsequence of the corresponding swing-based sequence. What is the complement of this subsequence, in other words, what are the terms of the swing-based sequence which are not just the double of the binomial-based sequence?

Starting with the most simple case, A005836 versus A196747, we find

1, 7, 19, 25, 55, 61, 73, 79, 163, 169, 181, 187, 217, 
223, 235, 241, 487, 493, 505, 511, 541, 547, 559, 565, 
649, 655, 667, 673, 703, 709, 721, 727, 1459, 1465 

And this sequence is in OEIS! A196747 - 2*A005836 = A055246.

A055246 is used for boundaries of open intervals which have to be erased in the Cantor middle third set construction.

An unexpected relation! Clearly we could consider along the same line the other pairs of sequences.

A181637 - 2*A129508 = 1, 61, 73, 511, 1513, 1621, 6373, 
6553, 13123, 13771, 15073, 15121, 15253, 15301, 39373

References

Peter Luschny, Divide, swing and conquer the factorial and the lcm{1,2,...,n}, preprint, April 2008.