Multifactorial Pseudoprimes

 

In the preceding article, we considered introducing the multifactorial n!2 in combination with n! and n# in order to produce sequences of numbers with built-in sieves. Now let us focus more directly on multifactorials alone. The standard form n!m±1, when a pseudoprime has been located, succumbs straightforwardly to the familiar Brillhart-Lehmer-Selfridge primality tests, and so has been subject to substantial investigation by many contributors. However, we are not necessarily interested in full primality at this point, and so it behoves us to consider slight deviations from this in our search for interesting pseudoprimes.

 

First, we remain with the n!2 case. If n is odd, then n!2 is both odd and divisible by n#. The obvious move is to consider the form n!2±2, which is also odd and cannot be divisible by any prime less than or equal to n. In keeping with previous nomenclature, I call these defactos.

 

1!2+2 = 3 (prime)

 

1

3!2+2 = 5 (prime)

 

1

5!2+2 = 17 (prime)

5!2-2 = 13 (prime)

2

7!2+2 = 107 (prime)

7!2-2 = 103 (prime)

3

9!2+2 = 947 (prime)

 

3

 

15!2-2 (prime)

7

 

17!2-2 (prime)

8

 

19!2-2 (prime)

9

21!2+2 (prime)

 

11

23!2+2 (prime)

 

12

27!2+2 (prime)

 

15

 

51!2-2 (prime)

34

57!2+2 (prime)

 

39

 

73!2-2 (prime)

54

75!2+2 (prime)

 

56

 

89!2-2 (prime)

69

103!2+2 (prime)

 

83

 

131!2-2 (prime)

112

 

153!2-2 (prime)

136

169!2+2 (prime)

 

153

219!2+2 (prime)

 

211

245!2+2 (prime)

245!2-2 (prime)

241

 

333!2-2

350

 

441!2-2

489

461!2+2

 

516

 

463!2-2

519

695!2+2

 

839

 

825!2-2

1026

1169!2+2

 

1541

 

1771!2-2

2494

 

2027!2-2

2914

3597!2+2

 

5617

3637!2+2

 

5688

7495!2+2

 

12896

 

9157!2-2

16153

 

10875!2-2

19589

 

20515!2-2

39779

 

Now let’s branch out a bit. Consider n!m where m can be any positive integer (less than n for good measure). Then n, n-m, n-2m, etc. is an arithmetic sequence with difference m, or more precisely -m. Suppose p is a prime, and p is less than or equal to n/m. Then, by the Chinese Remainder Theorem, p will divide at least one member of the sequence. Hence n!m is automatically pre-sieved to n/m.  We may then consider deviations d from n!m such that n!m±d is odd and such that no odd prime can divide. If n is even, then n!m is even, and we can only choose d=1, which we have already excluded from consideration here. If n is odd, then n!m is even when m is odd and odd when m is even. Hence we consider the form n!m±2 for n odd and m even. The m=2 case is handled above. Let us now consider m = 4.

 

Since gcd(4,p) = 1 for all odd primes p, one of the sequence n, n+4, n+8, … ,n+4(p-1) is divisible by p. Hence if n³4p, n!4 is divisible by p and we have a sieve to n/4. In fact, if nºxmod4, where x is 1 or 3, then n!4 is divisible by all primes p<n where pºxmod4, and so the sieve is tighter than n/4. The following is a list of pseudoprimes for n>100.

 

 

125!4-2 (prime)

53

 

133!4-2 (prime)

58

143!4+2 (prime)

 

63

 

153!4-2 (prime)

69

 

157!4-2 (prime)

71

169!4+2 (prime)

 

77

185!4+2 (prime)

185!4-2 (prime)

86

 

201!4-2 (prime)

96

 

217!4-2 (prime)

105

 

223!4-2 (prime)

109

235!4+2 (prime)

 

116

259!4+2 (prime)

 

130

 

289!4-2

148

 

323!4-2

169

363!4+2

 

195

365!4+2

 

196

457!4+2

 

256

 

469!4-2

264

493!4+2

 

280

 

533!4-2

307

 

567!4-2

331

573!4+2

 

335

777!4+2

 

479

 

821!4-2

511

 

1001!4-2

644

1273!4+2

 

852

1275!4+2

 

854

1865!4+2

 

1325

 

1999!4-2

1435

 

2523!4-2

1874

 

2533!4-2

1883

 

2827!4-2

2135

 

2843!4-2

2148

3621!4+2

 

2831

4523!4+2

 

3645

 

4821!4-2

3918

5291!4+2

 

4353

5845!4+2

 

4872

7185!4+2

 

6149

 

8153!4-2

7089

 

8947!4-2

7870

10183!4+2

 

9100

 

12739!4-2

11693

12845!4+2

 

11802

15057!4+2

 

14094

16281!4+2

 

15378

17945!4+2

 

17139

18771!4+2

 

18019

 

19353!4-2

18642

22479!4+2

 

22018

 

22929!4-2

22508

 

Let us now consider m=6. A slight problem now arises, that of divisibility by 3. If nº1mod3, then n!6+2 is divisible by 3, and if nº2mod3, then divisibility alternates between n!6+2 and n!6-2 depending on n. However, the remainder of the sieve to n/6 is intact. Again, I list pseudoprimes for n>100.

 

 

157!6-2 (prime)

48

197!6+2 (prime)

 

63

213!6+2 (prime)

 

69

221!6+2 (prime)

 

72

245!6+2 (prime)

 

82

 

265!6-2 (prime)

89

 

267!6-2 (prime)

91

279!6+2 (prime)

 

95

 

327!6-2 (prime)

115

 

539!6-2

208

 

555!6-2

216

 

621!6-2

246

 

715!6-2

290

845!6+2

 

353

 

921!6-2

390

927!6+2

 

393

 

979!6-2

419

 

1633!6-2

758

 

1821!6-2

860

2055!6+2

 

988

 

2259!6-2

1102

 

2697!6-2

1349

 

2809!6-2

1413

 

2863!6-2

1444

2895!6+2

 

1463

 

2935!6-2

1486

3615!6+2

 

1885

 

4213!6-2

2242

 

4351!6-2

2326

5613!6+2

 

3104

 

5937!6-2

3307

 

6885!6-2

3780

 

8743!6-2

5113

 

10761!6-2

6455

12753!6+2

 

7806

 

15159!6-2

9468

15737!6+2

 

9871

 

17685!6-2

11243

17813!6+2

 

11333

18545!6+2

 

11853

22629!6+2

 

14789

 

Another issue regarding m=6 is that, purely because there are less numbers involved in the product n!6, as n rises, n!6 rises much more slowly that for n!2. For this reason, no larger values of m are considered.

 

Returning to the general case of n!m for n odd and m even, we require our deviation d to ensure that n!m±d is not divisible by any (small) prime up to n/m. We have until now chosen d=2. However, it is obvious that d can take any value of 2x for x>0 and retain this property. With a little extra thought, we can obtain an even more general formula, as follows. Since n!m is divisible by every prime p up to n/m, any deviation x for which p does not divide x will preserve the sieve effect. If gcd(m,x)=1 then any primes dividing x will divide n!m±x (as long as x is no greater than n/m), and so we require gcd(m,x)>1. On the other hand, if gcd(n,x)>1 then there will be a prime that divides both x and n!m±x, and so we require gcd(n,x)=1. Obviously, we additionally require that the values for n, m and x guarantee that the overall formula is odd. We may therefore consider the following values.

 

For m=2, x=2y, n odd

For m=3, x=3y, n not divisible by 3

For m=4, x=2y, n odd

For m=5, x=5y, n not divisible by 5

For m=6, x=2y, n odd, or x=3y, n even and not divisible by 3, or x=6y, n odd and not divisible by 3

 

For m=3, let us restrict ourselves to x=3. I list probable primes for n>1000.

 

 

1039!3-3

896

 

1045!3-3

902

 

1190!3-3

1050

 

1595!3-3

1474

 

1679!3-3

1564

 

1772!3-3

1665

 

1789!3-3

1683

1952!3+3

 

1861

2197!3+3

 

2132

 

2410!3-3

2370

2428!3+3

 

2391

 

2920!3-3

2953

2960!3+3

 

2999

3430!3+3

 

3548

4618!3+3

 

4975

 

5039!3-3

5492

7478!3+3

 

8576

 

7919!3-3

9147

8209!3+3

 

9525

8422!3+3

 

9803

9235!3+3

 

10873

 

10462!3-3

12506

11107!3+3

 

13373

 

11846!3-3

14373

13481!3+3

 

16609

18194!3+3

 

23204

19229!3+3

 

24678

23293!3+3

 

30539

 

For m=4, let us consider x=4 only. The following lists pseudoprimes for n>1000.

 

1023!4+4

 

661

 

1057!4-4

686

1107!4+4

 

724

 

1433!4-4

977

 

1453!4-4

993

1517!4+4

 

1044

 

1519!4-4

1046

1557!4+4

 

1076

1625!4+4

 

1130

 

1759!4-4

1238

 

3047!4-4

2325

 

3561!4-4

2777

 

4151!4-4

3307

4215!4+4

 

3364

5297!4+4

 

4359

6291!4+4

 

5294

6499!4+4

 

5492

 

7025!4-4

5995

7357!4+4

 

6315

11639!4+4

 

10570

 

11917!4-4

10853

 

11971!4-4

10908

12963!4+4

 

11924

13989!4+4

 

12983

 

15295!4-4

14343

15825!4+4

 

14898

 

18919!4-4

18177

 

19449!4-4

18745

19993!4+4

 

19329

20535!4+4

 

19913

 

20765!4-4

20160

 

For m=5, let us restrict ourselves to x=5. Again, I list probable primes for n>1000 only.

 

 

1012!5-5

522

1017!5+5

 

525

1033!5+5

 

535

1104!5+5

 

578

1342!5+5

 

725

1371!5+5

 

743

 

1388!5-5

754

1426!5+5

 

778

1918!5+5

 

1095

2146!5+5

 

1246

 

2207!5-5

1287

 

2619!5-5

1565

 

2714!5-5

1630

3081!5+5

 

1884

 

3229!5-5

1988

 

3689!5-5

2314

 

3967!5-5

2513

 

3992!5-5

2531

4263!5+5

 

2727

 

4588!5-5

2964

4962!5+5

 

3239

5112!5+5

 

3350

 

5704!5-5

3792

 

6133!5-5

4116

 

6139!5-5

4120

6269!5+5

 

4219

 

6842!5-5

4656

 

8397!5-5

5863

9829!5+5

 

6997

 

10141!5-5

7247

11494!5+5

 

8339

 

11831!5-5

8612

 

15948!5-5

12022

16671!5+5

 

12631

17623!5+5

 

13438

 

18322!5-5

14033

 

18721!5-5

14373

 

19004!5-5

14615

19672!5+5

 

15188

20572!5+5

 

15962

 

22177!5-5

17352

24698!5+5

 

19556

 

24888!5-5

19723

 

24922!5-5

19752

25227!5+5

 

20021

 

25617!5-5

20364

 

For m=6, we consider x=6 and then x=3 and x=4 for n>1000.

 

 

1517!6-6

697

 

1799!6-6

848

 

3355!6-6

1731

12049!6+6

 

7326

16457!6+6

 

10376

17143!6+6

 

10859

17543!6+6

 

11142

18391!6+6

 

11743

 

24619!6-6

16239

25829!6+6

 

17127

25945!6+6

 

17212

31307!6+6

 

21194

34601!6+6

 

23675

 

&

 

 

1360!6-3

614

1426!6+3

 

649

 

1502!6-3

689

 

1516!6-3

696

 

1568!6-3

724

 

1646!6-3

765

1682!6+3

 

785

1928!6+3

 

918

3596!6+3

 

1873

 

3628!6-3

1892

 

3716!6-3

1944

3796!6+3

 

1992

 

4048!6-3

2143

 

7982!6-3

4616

 

12776!6-3

7822

15058!6+3

 

9398

 

18070!6-3

11515

 

20594!6-3

13318

25654!6+3

 

16998

 

29902!6-3

20144

 

&

 

 

1025!6-4

442

1389!6+4

 

629

1423!6+4

 

647

1515!6+4

 

696

1871!6+4

 

887

2059!6+4

 

990

2677!6+4

 

1338

3095!6+4

 

1579

 

4263!6-4

2273

 

4365!6-4

2335

4473!6+4

 

2400

 

5175!6-4

2831

 

5655!6-4

3130

5691!6+4

 

3152

5927!6+4

 

3300

8149!6+4

 

4724

 

9221!6-4

5428

 

9327!6-4

5498

 

9681!6-4

5733

10789!6+4

 

6473

12171!6+4

 

7409

14683!6+4

 

9137

 

19685!6-4

12666

 

24777!6-4

24530

26383!6+4

 

26300

34227!6+4

 

35086

 

For higher values of m, the growth rates in the sequence n!m get lower and lower and so the amount of checking increases. The fastest rate of growth of course if for m=2, which we have investigated for d=2. Let us broaden this out

To consider d=2y for all y up to a “reasonable” limit of y=16. For y=4 and y=8 we have the following:

 

 

105!2-4 (prime)

85

 

171!2-4 (prime)

156

 

243!2-4

239

 

271!2-4

273

 

295!2-4

302

315!2+4

 

327

 

355!2-4

378

 

523!2-4

599

549!2+4

 

635

 

591!2-4

693

 

1211!2-4

1606

2059!2+4

 

2967

 

3073!2-4

4694

5543!2+4

 

9175

6937!2+4

 

11819

 

11157!2-4

20159

 

&

 

103!2+8 (prime)

 

83

 

143!2-8 (prime)

125

299!2+8

299!2-8

307

 

307!2-8

317

341!2+8

341!2-8

360

 

381!2-8

411

431!2+8

 

476

445!2+8

 

495

465!2+8

 

521

519!2+8

 

594

 

585!2-8

684

 

995!2-8

1278

 

1019!2-8

1314

 

1027!2-8

1326

1251!2+8

 

1668

 

2043!2-8

2940

2469!2+8

 

3654

2507!2+8

 

3719

2549!2+8

 

3790

 

4301!2-8

6883

 

6275!2-8

10555

6817!2+8

 

11589

8519!2+8

 

14894

 

11157!2-8

20159

 

11621!2-8

21100

 

12315!2-8

22515

 

From now on, I only list numbers that have at least 10000 digits, as the volume of probable primes greatly increases.

 

For higher values of y, we have:

 

6123!2+215

 

10267

 

6151!2-28

10320

 

6275!2-23

10555

6411!2+28

 

10814

 

6469!2-212

10924

 

6599!2-213

11172

6663!2+216

 

11294

6817!2+23

 

11589

6895!2+211

 

11739

6937!2+22

 

11819

 

7077!2-210

12089

 

7093!2-210

12119

7297!2+212

 

12513

 

7351!2-215

12617

7495!2+21

 

12896

 

7743!2-214

13377

 

7823!2-216

13533

7899!2+214

 

13681

 

8123!2-214

14118

 

8179!2-29

14228

8197!2+211

 

14263

 

8357!2-216

14576

 

8367!2-211

14596

8481!2+214

 

14820

8519!2+23

 

14894

8655!2+210

 

15162

8835!2+24

 

15516

 

8861!2-210

15568

 

8977!2-27

15797

 

8981!2-28

15805

 

9069!2-25

15979

 

9157!2-21

16153

 

9537!2-213

16908

 

9789!2-25

17410

10153!2+210

 

18137

10283!2+24

 

18398

10617!2+26

 

19069

 

10675!2-213

19186

10699!2+216

 

19234

 

10875!2-21

19589

 

11103!2-212

20050

 

11157!2-22

20159

 

11157!2-23

20159

 

I now push to even higher values of m, running from m=7 to 12, where we consider all possible values of d£m. For m=7, we only consider d=7.

 

18509!7+7

 

10138

 

18863!7-7

10354

19286!7+7

 

10612

 

20470!7-7

11340

 

22171!7-7

12392

 

22376!7-7

12519

 

23195!7-7

13029

 

25142!7-7

14248

 

25216!7-7

14294

 

25604!7-7

14539

 

26360!7-7

15015

26939!7+7

 

15382

26940!7+7

 

15382

 

For m=8, we can consider d=2, 4 or 8.

 

 

20671!8-2

10031

 

21539!8-2

10500

22631!8+8

 

11093

22753!8+4

 

11159

23349!8+2

 

11485

 

24487!8-8

12107

 

25371!8-4

12593

 

25371!8-8

12593

 

26787!8-8

13375

 

28377!8-2

14257

 

29147!8-4

14687

29347!8+2

 

14798

29477!8+2

 

14871

 

30149!8-8

15247

30181!8+2

 

15265

 

30365!8-8

15368

 

31369!8-4

15931

 

For m=9, we consider d=3 and 9.

 

 

23758!9-9

10407

 

23897!9-3

10475

24622!9+3

 

10828

 

26528!9-9

11762

 

26755!9-9

11873

27265!9+3

 

12125

 

27410!9-9

12196

 

28265!9-9

12618

28412!9+9

 

12691

28526!9+3

 

12747

29477!9+9

 

13219

 

30601!9-9

13778

 

30775!9-9

13865

31540!9+3

 

14247

 

For m=10, we have d=2, 4, 8, or 10 for odd n and d=5 for even n.

 

25235!10+2

 

10015

25247!10+2

 

10021

 

25453!10-10

10111

 

25575!10-4

10165

 

25831!10-10

10278

 

25969!10-8

10339

26029!10+10

 

10365

 

26159!10-4

10423

 

26164!10-5

10425

 

26225!10-8

10452

26329!10+2

 

10498

26583!10+4

 

10610

 

27033!10-2

10810

27675!10+2

 

11094

27768!10+5

 

11136

28043!10+10

 

11258

28402!10+5

 

11418

28547!10+10

 

11482

 

28601!10-2

11506

29463!10+10

 

11891

 

30082!10-5

12168

 

31245!10-2

12690

 

31957!10-2

13010

31968!10+5

 

13015

32023!10+10

 

13040

 

33215!10-4

13578

 

33289!10-2

13611

33391!10+2

 

13657

34302!10+5

 

14070

38876!10+5

 

16157

 

41226!10-5

17239

 

For m=11, we just have d=11.

 

 

27832!11-11

10149

28222!11+11

 

10307

 

28326!11-11

10349

 

29473!11-11

10814

32922!11+11

 

12223

 

34516!11-11

12880

35333!11+11

 

13217

 

Lastly, for m=12, d can be 2, 4, 6, 8 or 12 when n is odd, and 3 or 9 when n is even.

 

29769!12+8

 

10024

29881!12+6

 

10065

29936!12+3

 

10086

30839!12+12

 

10423

30933!12+8

 

10458

31232!12+9

 

10570

31313!12+12

 

10601

 

31622!12-3

10717

31699!12+4

 

10746

32051!12+12

 

10877

 

32335!12-8

10984

 

32356!12-9

10992

32587!12+6

 

11079

33225!12+8

 

11319

33437!12+8

 

11399

33775!12+12

 

11527

 

33844!12-9

11553

 

37106!12-9

12789

 

38668!12-9

13385

40912!12+9

 

14246

42712!12+3

 

14939

42800!12+3

 

14973

42982!12+9

 

15043

 

44176!12-9

15505

 

The benefits of being able to test more small numbers as m increase is offset by the slowing of the rate of growth. For m=12 and even n above, the effort in reaching 10000 digits is hugely more expensive than for lower m.

 

Last updated: 19/11/2010

 

Back to main page