Summarized Results for 100,043 “Safe” Prime Zero Omitted

March 1, 2005

General

All: 100,041 Graphs Primitive Root: 50,020 Graphs Not Primitive Root: 50,021 Graphs

Largest Cycle: 100,042 (g = 20, 812 and 94, 034) Longest Tail: 1,448 (g = 89, 339) Shortest Maximum Cycle: 1 (g = 72, 116 and 91, 980 and 95, 997)

Number of Components

Observed All:

923, 855/100, 041 ≈ 9.23

Maps

Theoretical:

\frac{1}{2} log n = \frac{1}{2} log 100, 043 ≈ 5.76

Observed Not PR:

319, 587/50, 021 ≈ 6.39

Permutations

Theoretical:

∑_{i=1}^{100,043} \frac{1}{i} ≈ 12.09

Observed PR:

604, 268/50, 020 ≈ 12.08

Number of Cyclic Nodes

Observed All:

5, 023, 873, 923/100, 041 ≈ 50, 218.15

Maps

Theoretical:

\sqrt{πn/2} = \sqrt{π100, 043/2} ≈ 396.418

Observed Not PR:

19, 773, 083/50, 021 ≈ 395.296

Permutations

Theoretical:

100, 042

Observed PR:

5, 004, 100, 840/50, 020 = 100, 042

Number of Tail Nodes

Observed All:

4, 984, 427, 799/100, 041 ≈ 49, 823.85

Maps

Theoretical:

n − \sqrt{πn/2} = 100, 042 − \sqrt{π100, 042/2} ≈ 99, 645.58

Observed Not PR:

4, 984, 427, 799/50, 021 ≈ 99, 646.70

Permutations

Theoretical:

0

Observed PR:

0/50, 020 = 0

Number of Terminal Nodes

Observed All:

2, 502, 150, 460/100, 041 ≈ 25, 011.25

Maps

Theoretical:

e^{−1}n = e^{−1} ∗ 100, 042 ≈ 36, 803.395

Observed Not PR:

2, 502, 150, 460/50, 021 = 50, 021.99996

All values of g except 100, 042 that were not PR had exactly 50, 022. g = 100, 042 had a total of 100, 041. Since 100, 042 ≡ −1 mod n this exception makes sense. In the other cases, obviously, g^{0} ≡ g^{p−1} ≡ 1 mod n.

Permutations

Theoretical:

0

Observed PR:

0/50, 020 = 0

Number of Image Nodes

Observed All:

100, 043 − 25, 012.25 ≈ 75, 030.75

Maps

Theoretical:

(1 − e^{−1})n = (1 − e^{−1}) ∗ 100, 043 ≈ 63, 239.24

Observed Not PR:

100, 043 − 50, 022.99996 ≈ 50, 020.00

The notes under Number of Terminal Nodes also apply here since Terminal Nodes+Image Nodes = n.

Permutations

Theoretical:

n − 1 = 100, 0437 − 1 = 100, 042

Observed PR:

100, 043 − 1 = 100, 042

Average Tail Length

Observed All:

197.95

Maps

Theoretical:

\sqrt{πn/8} = \sqrt{π100, 042/8} ≈ 198.21

Observed Not PR:

197.96

Have to double check with new run that does not include 0.

Permutations

Theoretical:

0

Observed PR:

0

Average Cycle Length

Observed All:

25, 089.18

Maps

Theoretical:

\sqrt{πn/8} = \sqrt{π100, 043/8} ≈ 198.21

Observed Not PR:

198.315

Permutations

Theoretical:

\frac{n + 1}{2} = \frac{100, 043 + 1}{2} = 50, 022

Observed PR:

49, 980.6

Maximum Cycle Length

Observed All:

31, 321.1

Maps

Theoretical:

c_{1}\sqrt{n} ≈ 0.78248\sqrt{100, 043} ≈ 247.495

Observed Not PR:

247.256

Permutations

Theoretical:

0.62432965n = 0.62432965 ∗ 100043 ≈ 62, 495.81

Observed PR:

62, 395.5

Maximum Tail Length

Observed All:

271.41

Maps

Theoretical:

c_{2}\sqrt{n} ≈ 1.73746\sqrt{100, 042} ≈ 549.55

Observed Not PR:

541.816

Have to double check with new run that does not include 0.

Permutations

Theoretical:

0

Observed PR:

0