The Carmichael numbers up to 1021
Richard G.E. Pinch
2 Eldon Road, Cheltenham, Glos GL52 6TU, U.K.

rgep@chalcedon.demon.co.uk

Introduction

Statistics

We extend our previous computations to show that there are 20138200
Carmichael numbers up to 1021. As before, the numbers were generated bya back-tracking search for possible prime factorisations together with a “largeprime variation”. We present further statistics on the distribution of Carmichaelnumbers.

n1213
14
15
16
1718192021C(n) 8241 19279 44706 105212 246683 585355 1401644 3381806 8220777 20138200

Organisation of the search
We used improved versions of strategies first described in [2].
The principal search was a depth-first back-tracking search over possible sequences of primes factors p1, . . . , pd . Put Pr = ∏ri=1 pi, Qr = ∏di=r+1 pi and
Lr = lcm {pi − 1 : i = 1, . . . , r}. We find that Qr must satisfy the congruence
N = Pr Qr ≡ 1 mod Lr and so in particular Qd = pd must satisfy a congruence
modulo Ld−1: further pd − 1 must be a factor of Pd−1 − 1. We modified this toterminate the search early at some level r if the modulus Lr is large enough tolimit the possible values of Qr , which may then be factorised directly.
We also employed the variant based on proposition 2 of [2] which determines
the finitely many possible pairs (pd−1, pd ) from Pd−2. In practice this was useful only when d = 3 allowing us to determine the complete list of Carmichaelnumbers with three prime factors up to 1021.

Distribution of Carmichael numbers up to 1021.
X3
4
3
10470
5
124
6
23
19
7
47
55
8
84144
9172
314
10335
619
11590
1179
12
1000
2102
13
1858
3639
1432846042
1560839938
16 10816 16202
17 19539 25758
18 35586 40685
19 65309 63343
20 120625 98253
21 224763 151566

567
8
910
11 12
total
0
00
0
0
0
00
1
00
0
0
0
000
7
00
0
0
0
000
16
1
00
0
0000
43
3
00
0
0
00010527
0000000255
146
1400
0
000
646
492
99
20000015471336
459
41000003605
3156
1714
262
700008241
7082
5270
1340
89
1
000
19279
14938
14401
5359
655
27
000
44706
29282
36907
19210
3622
170000105212
55012
86696
60150
16348
1436
2300
246683100707 194306 172234
63635
8835
340
10585355
178063 414660 460553 223997
44993
3058
49
0 1401644
306310 849564 1159167 720406 196391 20738
576
2 3381806
514381 1681744 2774702 2148017 762963 114232 5804 56 8220777
846627 3230120 6363475 6015901 2714473 547528 42764 983 20138200

Values of C(X) and Cd (X) for X in powers of 10 up to 1021.
We have shown that there are 20138200 Carmichael numbers up to 1021, allwith at most 12 prime factors. We let C(X) denote the number of Carmichaelnumbers less than X and C(d, X) denote the number with exactly d prime factors. Table 1 gives the values of C(X) and Table 2 the values of C(d, X) for X
in powers of 10 up to 1021.

They proved that lim inf k ≥ 1 and suggested that lim sup k might be 2, although
they also observed that within the range of their tables k(X) is decreasing:
Pomerance [4],[5] gave a heuristic argument suggesting that lim k = 1. The
decrease in k is reversed between 1013 and 1014: see Figure 1. We find no clear
support from our computations for any conjecture on a limiting value of k.
n logC (10n) /(n log 10) C(10n)/C(10n−1)4
0.211277.000
50.24082
2.286
60.272242.688
70.28874
2.441
80.30082
2.429
90.31225
2.533
100.318952.396
11
0.323362.330
120.326332.286
130.329622.339
140.332172.319
150.334802.353
160.33700
2.335
170.339262.373
180.341482.394
190.343632.413
200.345742.431
210.347812.450

k (10n)2.19547
2.07632
1.97946
1.93388
1.90495
1.87989
1.86870
1.864211.86377
1.86240
1.86293
1.86301
1.86406
1.86472
1.865221.86565
1.86598
1.86619

C(X) as a power of X, the growth of C(X) and the function k(X) for
X = 10n up to 1021.

Conclusion
We consider that there is no clear evidence that k(x) approaches any limit.

References
A large prime variation
Finally we employed a different search over large values of pd , in the range
2.106 < pd < 109.5, using the property that Pd−1 ≡ 1 mod (pd − 1).
If q is a prime in this range, we let P run through the arithmetic progression P ≡ 1 mod q − 1 in the range q < P < X/q where X = 1021. We firstcheck whether N = Pq satisfies 2N ≡ 2 mod N: it is sufficient to test whether
2N ≡ 2 mod P since the congruence modulo q is necessarily satisfied. If thiscondition is satisfied we factorise P and test whether N ≡ 1 mod λ (N).
The approximate time taken for X t ≤ q < X 1/2 is∑

X t <q<X 1/2X
≈ X 1−t .
q2k(X) versus log10 X.
In Table 3 and Figure 1 we tabulate the function k(X), defined by Pomerance,Selfridge and Wagstaff [3] bylog X log log log XC(X) = X exp −k(X).
log log X[1] R.A. Mollin (ed.), Number theory and its applications, Dordrecht, Kluwer
Academic, 1989, Proceedings of the NATO Advanced Study Institute on
Number Theory and Applications.
[2] Richard G.E. Pinch, The Carmichael numbers up to 1015, Math. Comp. 61(1993), 381–391, Lehmer memorial issue.
[3] C. Pomerance, J.L. Selfridge, and S.S. Wagstaff jr, The pseudoprimes up to25.109, Math. Comp. 35 (1980), no. 151, 1003–1026.
[4] Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37(1981), 587–593.
[5], Two methods in elementary analytic number theory, in Mollin [1],Proceedings of the NATO Advanced Study Institute on Number Theory andApplications, pp. 136–161.