Probable
Co-Primes

In the preceding article, I considered searching for probable
primes amongst numbers of the form n!m±x, with the
restrictions of gcd(m,x)>1 & gcd(n,x)=1 due to divisibility rules. For
example, we looked at n!2±2 for n odd.
However, it is obvious that when n is even, the sieve effect (i.e. the form not
being divisible by any prime less than n/2) is still in place, except for a
single factor of 2. Hence an additional possible source of probable primes is
found in numbers of the form (n!2±2)/2, where the
divide sign signifies Euclidean division. Clearly, this form lends itself to
proof of primality using BLS, as do analogous forms for m = 3, 4, and 5.
However, we can generalise to more suitable forms that do not.

We are now interested in
numbers of the form (n!m±x)/y, where
gcd(m,x)>1 (a necessity for the sieve effect to remain) and y divides n!m±x, and also requiring that y
¹ x. To keep the
number of possibilities manageable, we also restrict ourselves to x £ m.

The m = 6 case provides us
with our first opportunity, in that there are multiple possibilities because of
the interplay between divisors 2 and 3 which will define the divisor y. We will
look at this from a slightly different perspective, and consider the
divisibility patterns of n!6 first. Reduced modulo 2, n!6 alternates between 0
and 1, whereas modulo 3, n!6 rotates between 0, 1 and (-1)^{s} where s =
[n/6]+1. Since this last term repeats
over a cycle of length 12, we have the following two sequences (starting at n =
0 mod 12):

For divisibility by 2: 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

For divisibility by 3: 0, 1, 2, 0, 1, 2, 0, 1, 1, 0, 1, 1

To find out about the
divisibility of a particular form, all we need to do is offset these two sequences.
Consider n!6+2. These sequences become

For 2, no change: 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

For 3, shift by 2: 2, 0, 1, 2, 0, 1, 2, 0, 0, 2, 0, 0

For a number to be divisible
by 2, and not 3, we read off where the first line has a zero and the second
line does not, which occurs at n = 0, 2 & 6 mod 12. For a number to be
divisible by 3 and not 2, it’s vice-versa, which gives 1, 7 & 11 mod 12.
For a number to be divisible by 2 and 3, we read off 4, 8 and 10 mod 12, and
for a number to be neither divisible by 2 nor 3, we have 3, 5 and 9 mod 12.

We repeat this process for
each form under consideration, noting that certain modular sequences can be
re-used, for example, the mod 3 sequence for n!6-4 is the same as that for
n!6+2.

For n!6-2 (and n!6+4), the sequences
become:

For 2, no change: 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

For 3, shift by 1: 1, 2, 0, 1, 2, 0, 1, 2, 2, 1, 2, 2

Thus, for divisibility by 2 and not 3, we have : 0, 4, 6, 8, 10

for divisibility by 3 and not 2, we have: 5

for divisibility by 2 and 3, we have: 2

neither divisible by 2 nor 3: 1, 3, 7, 9, 11

For n!6+3 and n!6-3, the mod 2 sequence shifts
by 1 and the mod 3 sequences coincide, giving

for divisibility by 2 and not 3, we have : 1, 5, 7, 11

for divisibility by 3 and not 2, we have: 0, 6

for divisibility by 2 and 3, we have: 3, 9

neither divisible by 2 nor 3: 2, 4, 8, 10

For n!6+6 and n!6-6, both original sequences
remain unchanged, giving

for divisibility by 2 and not 3, we have : 2, 4, 8, 10

for divisibility by 3 and not 2, we have: 3, 9

for divisibility by 2 and 3, we have: 0, 6

neither divisible by 2 nor 3: 1, 5, 7, 11

It is then easy to construct a list of the
forms that we wish to search in order to find probable primes, noting that
certain combinations can be ignored. In particular, we are not interested when
neither 2 nor 3 are divisors, since we have already studied the general case
elsewhere.

For x = 2 or 4 above,
possible divisibility by higher powers of 3 has not been ruled out. Knowledge
of this is not explicitly available unless we consider the n!6 sequence mod 9,
which has a repeat cycle of length 36:

n!6 mod 9: 0
1 2 0
4 5 0
7 7 0
4 1 0
1 8 0
1 8 0
1 7 0
4 4 0
7 2 0
4 8 0
1 1 0
1 1

We are interested, when the offsets
+2, -2, +4 and -4 are made, where the
sequences are divisible by 3:

n!6 mod 9: 0
1 2 0
4 5 0
7 7 0
4 1 0
1 8 0
1 8 0
1 7 0
4 4 0
7 2 0
4 8 0
1 1 0
1 1

+2 offset: 3 6 9
9 6 3 3 3 3
9 6 6
9 6 3
3 3 3

-2 offset: 9 3 6 6 9 6

+4 offset: 6 9 3 3 6 3

-4 offset: 6 9 3
3 9 6
6 6 6
3 9 9
3 9 6
6 6 6

Note that these values only
represent divisibility by 3 and bear no relation to divisibility by 2.

If we combine these with the
restrictions already known:

n!6+2 is divisible by 3 and
not 9 and not 2 at n = 1, 11, 13,
19, 23, 31, 35 mod 36

n!6+2 is divisible by 3 and
not 9 and 2 at n = 4, 10, 16, 22, 28, 32,
34 mod 36

n!6-2 is divisible by 3 and not
9 and not 2 at n = 5, 17, 29 mod 36

n!6-2 is divisible by 3 and not
9 and 2 at n = 14 mod 36

and similarly for x = 4:

n!6+4 is divisible by 3 and
not 9 and not 2 at n = 17, 29 mod
36

n!6+4 is divisible by 3 and
not 9 and 2 at n = 2, 14, 26 mod 36

n!6-4 is divisible by 3 and not
9 and not 2 at n = 1 ,7, 11, 13,
19, 25, 31, 35 mod 36

n!6-4 is divisible by 3 and not
9 and 2 at n = 8, 16, 20, 32, 34 mod 36

In order to determine when
we can divide exactly by 9 and no higher power of 3, we would have to consider
the sequence of n!6 modulo 27, which has a repeat cycle length of 108. It would
be easy enough to write a computer program to generate all the possibilities
but at some point we have to call a halt to the theory and start searching for
probable primes.

If we study the set of
possibles above for x = 6, it is obvious that this form is either divisible by
2 and no higher power of 2, or not divisible by 2 at all, so there are no
refinements to be made. However, for x = 3, there is no such restriction, and
since we stand to ignore half of the search space, it is worth considering the
n!6 sequence modulo 4. In fact, this also repeats with cycle length 12, but let
us push as far as mod 8, which has a length 24 cycle. We are only interested in
the cases where the offset is divisible by 2:

n mod 24: 0
1 2 3
4 5 6
7 8 9
10 11 12 13
14 15 16
17 18 19
20 21 22 23

n!6 mod 8: 0
1 0 3
0 5 0
7 0 3
0 7 0
3 0 5
0 7 0
1 0 1
0 1

+3 offset:
4 6 8 2 6 2 6 8 2 4 4 4

-3 offset:
6 8 2
4 6 4 8 2 4 6 6 6

Combining this with the
earlier results mod 2 & mod 3, we have (modulo 24):

For n!6+3: divisible by exactly 2 and not 3: 7, 11, 13, 17

divisible by exactly 4 and not 3: 1, 19, 23

divisible by at least 8 and not 3: 5

divisible by exactly 2, and 3: 3, 9

divisible by exactly 4, and 3: 21

divisible by at
least 8, and 3: 15

and similarly for n!6-3:

divisible by
exactly 2 and not 3: 1, 5,
19, 23

divisible by exactly 4 and not 3: 7, 11, 17

divisible by at least 8 and not 3: 13

divisible by exactly 2, and 3: 15, 21

divisible by exactly 4, and 3:

divisible by at
least 8, and 3: 3, 9

Where divisibility by at
least 8 is identified, I performed a bit of testing, which suggests that higher
powers of 2 feature regularly, except for the n!6+3, n = 15 mod 24 case, which
appears to be exact.

For x = 6, no additional
allowances have to be made since divisibility by 2 or 3 is either exact or does
not occur.

The complete set of n!6
forms that survive a sieve to n/6 and are worth considering is:

(n!6+2)/3 for n = 1, 11, 13,
19, 23, 31, 35 mod 36

(n!6-2)/3 for n = 5, 17, 29 mod
36

(n!6+2)/6 for n = 4, 10, 16,
22, 28, 32, 34 mod 36

(n!6-2)/6 for n = 14 mod 36

(n!6+4)/3 for n = 17, 29 mod
36

(n!6-4)/3 for n = 1, 7, 11, 13,
19, 25, 31, 35 mod 36

(n!6+4)/12 for n = 2, 14, 26
mod 36

(n!6-4)/12 for n = 8, 16, 20, 32,
34 mod 36

(n!6+3)/2 for n = 7, 11, 13,
17 mod 24

(n!6-3)/2 for n = 1, 5, 19, 23
mod 24

(n!6+3)/4 for n = 1, 19, 23
mod 24

(n!6-3)/4 for n = 7, 11, 17 mod
24

(n!6+3)/6 for n = 3, 9 mod
24

(n!6-3)/6 for n = 15, 21 mod 24

(n!6+3)/12 for n = 21 mod 24

(n!6-3)/12 for n = X (none)

(n!6+3)/24 for n = 15 mod 24
(for luck)

(n!6+6)/2 for n = 2, 4, 8,
10 mod 12

(n!6-6)/2 for n = 2, 4, 8, 10 mod
12

(n!6+6)/3 for n = 3, 9 mod
12

(n!6-6)/3 for n = 3, 9 mod 12

All these forms can be
brought together modulo 72 for convenience.

A blanket search through all
numbers of the form n!6±x for x = 2, 3,
4, and 6 for probable primes, with logical restrictions (n even when x =2 or 4,
divisible by 2 and not 3 when x = 3 and divisible by neither 3 nor 2 when x =
6) would cover 41.7% of all possible combinations. Searching through the form
(n!6±x)/y for y = 2,
3, or 6 and y ¹ x using the
arguments mod 12 and disregarding divisibility by higher powers of 2 and 3
would require searching through the same percentage (40 out of a possible 96).
Using the additional arguments mod 24 and 36, and considering known exact
division only brings this down to 204 out of 576, which is 35.416’%.

Although this still appears
to be a lot of work to check, I have found that the best way to proceed is by
using a simple program to generate, for n in specific search ranges, a list of
the numbers that need to be checked, and then submitting this to a primality
tester such as pfgw.

(17051!6+3)/2 |
10794 |

(17291!6+2)/3 |
10964 |

(17523!6+3)/6 |
11128 |

(17839!6-3)/4 |
11351 |

(19796!6+2)/6 |
12746 |

(20069!6-2)/3 |
12941 |

(20397!6-6)/3 |
13177 |

(21812!6+2)/6 |
14197 |

(22247!6+3)/4 |
14511 |

(22642!6-6)/2 |
14798 |

(23407!6-3)/4 |
15354 |

(23553!6+6)/3 |
15460 |

(23899!6-3)/2 |
15713 |

(24016!6+6)/2 |
15798 |

(24333!6+3)/12 |
16030 |

(25580!6+6)/2 |
16944 |

(26150!6+4)/12 |
17363 |

(27794!6+6)/2 |
18577 |

(27935!6+2)/3 |
18681 |

(28751!6-3)/2 |
19287 |

(32391!6+3)/24 |
22008 |

For m = 6, we could further
search amongst larger values x = 8, 12, 16, 18, etc., but you’ve got to draw
the line somewhere.

For m = 10, we consider x =
2, 4, 5, 8 and 10. For n = 0 & 1 mod 5, n!10 is always 0 and 1. However,
for n = 2 mod 5, n!10 cycles round {2,4,3,1}. Similarly, for n = 3 mod 5, n!10
cycles round the set {3,4,2,1}. For n = 4 mod 5, n!10 alternates between 4 and
1. This is just a fancy way of saying that n!10 mod 5 repeats with cycle length
40. It so happens that 40 is the cycle length of n!10 both mod 4 and mod 8, so
we consider the higher of these.

position

for mod 5: 0, 1, 2, 3, 4, 0,
1, 2, 3, 4, 0, 1, 4, 4, 1, 0, 1, 4, 4, 1, 0, 1, 3, 2, 4, 0, 1, 3, 2, 4, 0, 1,
1, 1, 1, 0, 1, 1, 1, 1

for mod 8: 0, 1, 0, 3, 0, 5,
0, 7, 0, 1, 0, 3, 0, 7, 0, 3, 0, 7, 0, 3, 0, 7, 0, 1, 0, 3, 0, 5, 0, 7, 0, 1,
0, 1, 0, 1, 0, 1, 0, 1

For x = 2, 4 and 8,
divisibility by the exact power of 2 contained in x is satisfied at every even
position, and so we are only interested when 5 is also a divisor. For n!10+2,
this is identified when the above mod 5 sequence has value 3, which occurs at
positions 3, 8, 22 and 27. The odd values denote y = 5 and the even values y =
10. Similarly, we have divisibility by 5:

For n!10-2 at: 2, 7, 23 and 28

For n!10+4 at: 1, 6, 11, 14, 16, 19, 21, 26, 31, 32, 33, 34,
36, 37, 38 and 39

For n!10-4 at: 4, 9, 12, 13, 17, 18, 24 and 29

For n!10+8 at: 2, 7, 23 and 28

For n!10-8 at: 3, 8, 22 and 27

When x itself is divisible
by 5, we are interested when the offset mod 8 sequence is divisible by exactly
2, exactly 4 or by 8.

For n!10+5, exactly 2 at: 1, 5, 9, 23, 27, 31, 33, 35,
37 and 39

exactly 4 at: 7, 13, 17, 21 and 29

by 8 at: 3, 11, 15, 19 and 25

For n!10-5: exactly 2 at: 3, 7, 11, 13, 15, 17, 19, 21, 25 and 29

exactly 4 at: 1, 9, 23, 31, 33, 35, 37 and 39

by 8 at: 5 and 27

When the position number is
divisible by 5, we take y = 5 * appropriate power of 2.

For x = 10, it is obvious
that only even values of n have divisibility by 2, and this is exact, hence we
have x = y, which is ignored, and when 5 divides n, no higher power of 5 can be
involved, so we take these when n is odd.

We thus have the following
set of forms to consider:

(n!10+2)/5 for n = 3 &
27 mod 40

(n!10+2)/10 for n = 8 &
22 mod 40

(n!10-2)/5 for n = 7 & 23 mod
40

(n!10-2)/10 for n = 2 & 28 mod
40

(n!10+4)/5 for n = 1, 11,
19, 21, 31, 33, 37 & 39 mod 40

(n!10+4)/20 for n = 6, 14,
16, 26, 32, 34, 36 & 38 mod 40

(n!10-4)/5 for n = 9, 13, 17 &
29 mod 40

(n!10-4)/20 for n = 4, 12, 18
& 24 mod 40

(n!10+8)/5 for n = 7 &
23 mod 40

(n!10+8)/40 for n = 2 &
28 mod 40

(n!10-8)/5 for n = 3 & 27 mod
40

(n!10-8)/40 for n = 8 & 22 mod
40

(n!10+5)/2 for n = 1, 9, 23,
27, 31, 33, 37 & 39 mod 40

(n!10+5)/10 for n = 5 &
35 mod 40

(n!10-5)/2 for n = 3, 7, 11, 13,
17, 19, 21 & 29 mod 40

(n!10-5)/10 for n = 15 & 25
mod 40

(n!10+5)/4 for n = 7, 13,
17, 21 & 29 mod 40

(n!10+5)/20 for n = X
(never)

(n!10-5)/4 for n = 1, 9, 23, 31,
33, 37 & 39 mod 40

(n!10-5)/20 for n = 35 mod 40

(n!10+10)/5 for n = 5, 15,
25 & 35 mod 40

(n!10-10)/5 for n = 5, 15, 25
& 35 mod 40

No account of the
possibility of divisibility by higher powers of 5 was taken during the above,
which will happen regularly. The above search space covers 81 out of a possible
400. If we were to remove any condition where exact division was not
guaranteed, we would only be left with 11 out of 160. Again, a simple program
is used to generate numbers for testing, and the following have been found:

(29444!10-4)/20 |
11883 |

(31813!10+5)/4 |
12945 |

(31835!10-10)/5 |
12955 |

(32517!10-5)/4 |
13263 |

(34131!10+4)/5 |
13992 |

(34893!10-5)/2 |
14338 |

(36648!10+2)/10 |
15138 |

(36857!10-5)/2 |
15233 |

(37243!10-8)/5 |
15409 |

For m = 12, the lengths of
the cycle patterns for the sequences n!12 modulo 4 and 3 are both equal to 24:

Mod 4: 0 1 0 3 0 1 0 3 0 1 0
3 0 1 0 1 0 1 0 1 0 1 0 1

Mod 3: 0 1 2 0 1 2 0 1 2 0 1
2 0 1 1 0 1 1 0 1 1 0 1 1

For offsets +2, -4, +8 are the same:

divisibility by 2 (to the
appropriate power) and not 3 at positions 0, 2, 6, 8, 12 & 18

divisibility by 3 and not 2
at positions 1, 7, 13, 17, 19 & 23

divisibility by 2 and 3 at
positions 4, 10, 14, 16, 20 & 22

divisibility by neither 2
nor 3 at positions 3, 5, 9, 11, 15 & 21

and for offsets -2, +4 and -8:

divisibility by 2 and not 3
at positions 0, 4, 6, 10, 12, 14, 16, 18, 20 & 22

divisibility by 3 and not 2
at positions 5 & 12

divisibility by 2 and 3 at
positions 2 & 8

divisibility by neither 2
nor 3 at positions 1, 3, 7, 9, 13, 15, 17, 19, 21 & 23

For offsets +3 and -9:

divisibility by 2 and not 3
(to the appropriate power) at positions 7 & 11

divisibility by 3 and not 2
at positions 0, 6, 12 & 18

divisibility by 2 and 3 at
position 3

divisibility by neither 2
nor 3 at positions 2, 4, 8, 10, 14, 16, 20 & 22

divisibility by (at least) 4
and not 3 at positions 1, 5, 13, 17, 19 & 23

divisibility by (at least) 4
and 3 at positions 9, 15 & 21

and for offsets -3 and +9:

divisibility by 2 and not 3
at positions 1, 5, 13, 17, 19 & 23

divisibility by 3 and not 2
at positions 0, 6, 12 & 18

divisibility by 2 and 3 at
position 9, 15 & 21

divisibility by neither 2
nor 3 at positions 2, 4, 8, 10, 14, 16, 20 & 22

divisibility by (at least) 4
and not 3 at positions 7 & 11

divisibility by (at least) 4
and 3 at position 3

For offsets ±6 and ±12:

divisibility by 2 (to the
appropriate power) and not 3 at positions 2, 4, 8, 10, 14, 16, 20 & 22

divisibility by 3 and not 2
at positions 3, 9, 15 & 21

divisibility by 2 and 3 at
position 0, 6, 12 & 18

divisibility by neither 2
nor 3 at positions 1, 5, 7, 11, 13, 17, 19 & 23

Ignoring when x = y, and
ignoring the possibility of division by higher powers of 3, leads us to a set
of possible forms that provides a search space of 120 out of every 336, which
is 36%. It so happens that the mod 8 cycle for n!12 repeats mod 48, and the mod
9 cycle repeats mod 72. I have therefore performed a similar, but more
elaborate, exercise using these bases, across the extended pattern mod 144
(available in spreadsheet). Note that for offsets of ±8, when a position is
divisible by 8 it must be exactly divisible by 8 and no higher power of 2,
since in this case n!12 must be divisible itself by a much higher power of 2.
This allows us to include patterns for y = 24. Similarly, for offsets of ±9, we can consider patterns
for y = 18 and y = 36. If we then enforce exact division in all cases with x ≠
y, we can restrict ourselves to 696 out of 2016 possibilities, which is 34.5 %.
I have created a program that produces test data speedily and accurately, and
am currently searching for probable primes of the form (n!12±x)/y using the exact
divisions obtained. The results so far may be found below.

(29901!12-12)/ 3 |
10073 |

(30165!12-6)/ 3 |
10171 |

(30304!12+12)/ 4 |
10223 |

(30334!12-6)/ 2 |
10234 |

(30363!12-12)/ 3 |
10245 |

(31077!12+12)/ 3 |
10512 |

(32715!12-3)/12 |
11127 |

Last updated: 19/11/2010