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

 

Back to main page