E050: Primorials and Euclid numbers: \(p\#\pm 1\) are usually composite

Preview figure for E050
Preview figure for E050

Tags: number-theory, counterexample-search, quantitative-exploration, visualization, primorial See: Valid Tags.

Highlights

  • Computes primorials \(p_k\#=\prod_{i\le k} p_i\) and Euclid-style numbers \(p_k\#\pm 1\).

  • Uses a probable-prime test to show “often composite” behavior early.

  • Finds small factor witnesses via bounded trial division for many early \(k\).

Goal

Demonstrate that Euclid-style numbers are coprime to small primes but are not reliably prime, and produce explicit factor witnesses.

Background (quick refresher)

Research question

For small \(k\), how often are \(p_k\#\pm 1\) prime (or probable prime), and how easy is it to find a small factor when they are composite?

Experiment design

  • Compute primorials for \(k\le k_{max}\).

  • Test \(p_k\#\pm 1\) with Miller–Rabin (probable prime).

  • If composite under MR, try to find a small trial-division factor as a concrete witness.

  • Plot \(\log_{10}(p_k\#\pm 1)\) and smallest factor witnesses (log scale).

Reproducibility

  • params.json records the run settings.

  • report.md summarizes the key findings.

  • figures/*.png contains the plots for the run.

Interpreting the results

  • “Probable prime” is not a proof; it’s a fast filter for this exploratory experiment.

  • Factor witnesses come from bounded trial division: not finding a factor is expected for some \(k\).

  • You should see early composite examples such as \(p_6\#+1=30031\) (with a small factor) under default bounds.

Published run snapshot

If this experiment is included in the docs gallery, include the published snapshot (report + params).

Parameters

  • k_max: 16

  • factor_prime_bound: 1000000

  • mr_bases: 2, 3, 5, 7, 11, 13, 17

Results

k

p_k# + 1

pp?

factor

p_k# - 1

pp?

factor

1

3

✅

—

1

❌

—

2

7

✅

—

5

✅

—

3

31

✅

—

29

✅

—

4

211

✅

—

209

❌

11

5

2311

✅

—

2309

✅

—

6

30031

❌

59

30029

✅

—

7

510511

❌

19

510509

❌

61

8

9699691

❌

347

9699689

❌

53

9

223092871

❌

317

223092869

❌

37

10

6469693231

❌

331

6469693229

❌

79

11

200560490131

✅

—

200560490129

❌

228737

12

7420738134811

❌

181

7420738134809

❌

229

13

304250263527211

❌

61

304250263527209

✅

—

14

13082761331670031

❌

167

13082761331670029

❌

141269

15

614889782588491411

❌

953

614889782588491409

❌

191

16

32589158477190044731

❌

73

32589158477190044729

❌

87337

Notes

  • pp? is probable prime under the chosen Miller–Rabin bases.

  • Factor witnesses are from bounded trial division (not a full factorization).

params.json (snapshot)
{
  "factor_prime_bound": 1000000,
  "k_max": 16,
  "mr_bases": [
    2,
    3,
    5,
    7,
    11,
    13,
    17
  ]
}

References

See Hardy and Wright [2008], The OEIS Foundation Inc. [2025], Prime Pages (UTM) [2025], Wikipedia contributors [2025].