This site is supported by donations to The OEIS Foundation.

# User:Peter Luschny/PrimeFactorsSwingingFactorial

## Contents

# 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:

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 is sequence A056040 and the central binomial is sequence A000984.

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.