THE CARMICHAEL NUMBERS UP TO 10^{17}

RICHARD G.E. PINCH

Abstract. We extend our previous computations to show that there are 585355 Carmichael numbers up to 10^{17}. As before, the numbers were generated by a back-tracking search for possible prime factorisations together with a “large prime variation”. We present further statistics on the distribution of Carmichael numbers.

1. Introduction

A Carmichael number N is a composite number N with the property that for every b prime to N we have b^{N−1} ≡ 1 mod N. It follows that a Carmichael number N must be square-free, with at least three prime factors, and that p − 1|N − 1 for every prime p dividing N: conversely, any such N must be a Carmichael number.

For background on Carmichael numbers and details of previous computations we refer to our previous paper [4]: in that paper we described the computation of the Carmichael numbers up to 10^{15} and presented some statistics. These computations have since been extended to 10^{16} [5] and now to 10^{17}, using similar techniques, and we present further statistics.

The complete list of Carmichael numbers up to 10^{17} is available from the author’s

web site at www.chalcedon.demon.co.uk.

2. Organisation of the search

We used improved versions of strategies described in [4].

The principal search was a depth-first back-tracking search over possible sequences of primes factors p_{1}, …, p_{d}. Put P_{r} = ∏_{i=1}^{r} p_{i}, Q_{r} = ∏_{i=r+1}^{d} p_{i} and L_{r} = lcm {p_{i} − 1 : i = 1, …, r}. We find that Q_{r} must satisfy the congruence N = P_{r}Q_{r} ≡ 1 mod L_{r} and so in particular Q_{d} = p_{d} must satisfy a congruence modulo L_{d−1}: further p_{d} − 1 must be a factor of P_{d−1} − 1. We modified this to terminate the search early at some level r if the modulus L_{r} is large enough to limit the possible values of Q_{r}, which may then be factorised directly.

We also employed the variant based on proposition 2 of [4] which determines the finitely many possible pairs (p_{d−1}, p_{d}) from P_{d−2}. In practice this was useful only when d = 3 allowing us to determine the complete list of Carmichael numbers with three prime factors up to 10^{18}. The count of these is 35586 (not 35585 as incorrectly reported in our preliminary work).

Finally we employed a different search over large values of p_{d}, in the range 10^{7} < p_{d} < 10^{9}, using the property that P_{d−1} ≡ 1 mod (p_{d}−1) and factorising the numbers in this arithmetic progression less than 10^{18}/p_{d}.

3. Statistics

We have shown that there are 585355 Carmichael numbers up to 10^{17}, all with at most 11 prime factors. We let C(X) denote the number of Carmichael numbers less than X and C(d, X) denote the number with exactly d prime factors. Table 1

Date: 23 August 2004.

\begin{matrix}n & C (10^{n}) \\ 3 & 1 \\ 4 & 7 \\ 5 & 16 \\ 6 & 43 \\ 7 & 105 \\ 8 & 255 \\ 9 & 646 \\ 10 & 1547 \\ 11 & 3605 \\ 12 & 8241 \\ 13 & 19279 \\ 14 & 44706 \\ 15 & 105212 \\ 16 & 246683 \\ 17 & 585355 \end{matrix}

Table 1. Distribution of Carmichael numbers up to 10^{17}.

\begin{matrix}X & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & total \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 4 & 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 \\ 5 & 12 & 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 16 \\ 6 & 23 & 19 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 43 \\ 7 & 47 & 55 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 105 \\ 8 & 84 & 144 & 27 & 0 & 0 & 0 & 0 & 0 & 0 & 255 \\ 9 & 172 & 314 & 146 & 14 & 0 & 0 & 0 & 0 & 0 & 646 \\ 10 & 335 & 619 & 492 & 99 & 2 & 0 & 0 & 0 & 0 & 1547 \\ 11 & 590 & 1179 & 1336 & 459 & 41 & 0 & 0 & 0 & 0 & 3605 \\ 12 & 1000 & 2102 & 3156 & 1714 & 262 & 7 & 0 & 0 & 0 & 8241 \\ 13 & 1858 & 3639 & 7082 & 5270 & 1340 & 89 & 1 & 0 & 0 & 19279 \\ 14 & 3284 & 6042 & 14938 & 14401 & 5359 & 655 & 27 & 0 & 0 & 44706 \\ 15 & 6083 & 9938 & 29282 & 36907 & 19210 & 3622 & 170 & 0 & 0 & 105212 \\ 16 & 10816 & 16202 & 55012 & 86696 & 60150 & 16348 & 1436 & 23 & 0 & 246683 \\ 17 & 19539 & 25758 & 100707 & 194306 & 172234 & 63635 & 8835 & 340 & 1 & 585355 \end{matrix}

Table 2. Values of C(X) and C(d, X) for d ≤ 10 and X in powers of 10 up to 10^{17}.

gives the values of C(X) and Table 2 the values of C(d, X) for X in powers of 10 up to 10^{17}.

We have used the same methods to calculate the smallest Carmichael number S_{d} with d prime factors for d up to 34. The results are given in Table 3. Heuristics suggest that a good approximation for S_{d} might be (2(d − 1))^{2(d−1)}. There is some support for this from Table 4.

In Table 5 and Figure 1 we tabulate the function k(X), defined by Pomerance, Selfridge and Wagstaff [6] by

C(X) = X exp (−k(X)\frac{log X log log log X}{log log X} ) .

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 [7],[8] gave a heuristic argument suggesting that lim k = 1. The decrease in k

\begin{matrix}d & N \\ 3 & 561 \\ 4 & 41041 \\ 5 & 825265 \\ 6 & 321197185 \\ 7 & 5394826801 \\ 8 & 232250619601 \\ 9 & 9746347772161 \\ 10 & 1436697831295441 \\ 11 & 60977817398996785 \\ 12 & 7156857700403137441 \\ 13 & 1791562810662585767521 \\ 14 & 87674969936234821377601 \\ 15 & 6553130926752006031481761 \\ 16 & 1590231231043178376951698401 \\ 17 & 35237869211718889547310642241 \\ 18 & 32809426840359564991177172754241 \\ 19 & 2810864562635368426005268142616001 \\ 20 & 349407515342287435050603204719587201 \\ 21 & 125861887849639969847638681038680787361 \\ 22 & 12758106140074522771498516740500829830401 \\ 23 & 2333379336546216408131111533710540349903201 \\ 24 & 294571791067375389885907239089503408618560001 \\ 25 & 130912961974316767723865201454187955056178415601 \\ 26 & 13513093081489380840188651246675032067011140079201 \\ 27 & 7482895937713262392883306949172917048928068129206401 \\ 28 & 1320340354477450170682291329830138947225695029536281601 \\ 29 & 379382381447399527322618466130154668512652910714224209601 \\ 30 & 70416887142533176417390411931483993124120785701395296424001 \\ 31 & 2884167509593581480205474627684686008624483147814647841436801 \\ 32 & 4754868377601046732119933839981363081972014948522510826417784001 \\ 33 & 1334733877147062382486934807105197899496002201113849920496510541601 \\ 34 & 260849323075371835669784094383812120359260783810157225730623388382401 \end{matrix}

Table 3. The smallest Carmichael numbers with d prime factors for d up to 34.

is reversed between 10^{13} and 10^{14}: see Figure 1. We find no clear support from our computations for any conjecture on a limiting value of k.

In Table 5 we also give the ratios C(10^{n})/C(10^{n−1}) investigated by Swift [10]. Swift’s ratio, again initially decreasing, also increases again before 10^{15}.

In Table 6 and Figure 2 we see that within the range of our computations C(X) is a slowly growing power of X: about X^{0.339} for X around 10^{17}.

In Table 7 we give the number of Carmichael numbers in each class modulo m for m = 5, 7, 11 and 12.

The largest prime factor of a Carmichael number up to 10^{17} is 223401361, dividing

99816335969903281 = 17 · 31 · 379 · 2237 · 223401361.

We have 223401361 = 99816335969903281^{0.4911}. The largest prime to occur as the smallest prime factor of a Carmichael number in this range is 380251, dividing

90256390764228001 = 380251 · 410761 · 577981.

We note that this number is of the form (25k +1)(27k +1)(38k +1) with k = 15210.

d \frac{log(S_{d})}{2 log 2(d−1) log(d−1)}

3  3.293621187
4  2.324869052
5  1.772215418
6  1.755823184
7  1.503593258
8  1.385943139
9  1.296862582
10  1.273113126
11  1.210794211
12  1.187291825
13  1.183842403
14  1.142841324
15  1.115637251
16  1.112255293
17  1.068846695
18  1.086833722
19  1.067861876
20  1.055266652
21  1.056211783
22  1.041906608
23  1.034833298
24  1.024202006
25  1.026042173
26  1.014073506
27  1.017122489
28  1.010169037
29  1.007224804
30  1.000945160
31  0.984182030
32  0.993535534
33  0.990337138
34  0.984854273

Table 4. The smallest Carmichael number with d prime factors compared to (2(d − 1))^{2(d−1)}.

We define the index of a Carmichael number N to be i(N) = (N − 1)/λ(N) where λ is the Carmichael function, the exponent of the multiplicative group. A result of Somer [9] implies that i(N) → ∞ as N runs through Carmichael numbers. In Table 8 we list the Carmichael numbers known to have index less than 100.

We define the Lehmer index of a number N to be ℓ(N) = (N −1)/ϕ(N). Lehmer’s totient problem asks whether there is a number of integral Lehmer index greater than 1 (that is, whether there is a composite N such that ϕ(N) divides N −1). Such a number would have to be a Carmichael number. See Guy [2] §B37 for further details.

The Carmichael numbers up to 10^{17} with Lehmer index ≥ 2 are listed in Table

THE CARMICHAEL NUMBERS UP TO 10^{17} 5

Figure 1. k(X) versus X (expressed in powers of 10).

n k (10^{n}) C(10^{n})/C(10^{n−1})
3 2.93319
4 2.19547  7.000
5 2.07632  2.286
6 1.97946  2.688
7 1.93388  2.441
8 1.90495  2.429
9 1.87989  2.533
10 1.86870  2.396
11 1.86421  2.330
12 1.86377  2.286
13 1.86240  2.339
14 1.86293  2.319
15 1.86301  2.353
16 1.86406  2.335
17 1.86472  2.373

Table 5. The function k(X) and growth of C(X) for X = 10^{n}, n ≤ 17.

6 RICHARD G.E. PINCH

Figure 2. C(X) as a power of X (expressed in powers of 10).

\begin{matrix}n & log C (10^{n}) /(n log 10) \\ 4 & .21127 \\ 5 & .24082 \\ 6 & .27224 \\ 7 & .28874 \\ 8 & .30082 \\ 9 & .31225 \\ 10 & .31895 \\ 11 & .32336 \\ 12 & .32633 \\ 13 & .32962 \\ 14 & .33217 \\ 15 & .33480 \\ 16 & .33700 \\ 17 & .33926 \end{matrix}

Table 6. C(X) as a power of X.

m c 25.10^{9} 10^{11} 10^{12} 10^{13} 10^{14}  10^{15}  10^{16}  10^{17}
5 0  203 312 627 1330 2773  5814 12200 25523
1 1652 2785 6575 15755 37467 90167 215713 520990
2  82 154 327  702 1484  3048  6094 12912
3  102 172 344  725 1463  3059  6285 12845
4  124 182 368  767 1519  3124  6391 13085
7 0  401 634 1334 2774 5891 12691 27550 60602
1 1096 1885 4613 11447 28001 69131 168856 414999
2  105 186 432  967 2109  4599 10011 21961
3  152 232 496 1055 2178  4707 10039 21918
4  129 211 450  985 2122  4592  9944 21832
5  138 222 454 1033 2224  4777 10125 21911
6  142 235 462 1018 2181  4715 10158 22132
11 0  335 547 1324 3006 7032 16563 38576 90731
1  640 1131 2770 6786 16548 40891 100071 248840
2  139 217 473 1068 2361  5338 12054 27268
3  142 220 457 1045 2348  5319 12186 27483
4  104 187 442 1026 2317  5261 11917 27276
5  152 243 466 1066 2370  5316 12194 27670
6  116 198 440 1061 2400  5384 12155 27362
7  122 195 458 1023 2223  5165 11853 26960
8  129 222 475 1107 2450  5449 12012 27639
9  131 218 465 1042 2285  5179 11835 27158
10  153 227 471 1049 2372  5347 11830 26968
12 1 2071 3462 7969 18761 43760 103428 243382 579215
3  0  0  1  2  2  5  5  7
5  20  32  64  124  228  448  805  1470
7  47  75 147  289  547  1027  1906  3589
9  25  36  60  103  165  294  560  1018
11  0  0  0  0  4  10  25  56

Table 7. The number of Carmichael numbers in each class modulo m for m = 5, 7, 11 and 12.

8 RICHARD G.E. PINCH

\begin{matrix}i & N & factors \\ 5 & 6601 & 7 · 23 · 41 \\ 7 & 561 & 3 · 11 · 17 \\ 18 & 42018333841 & 11 · 47 · 1049 · 77477 \\ 18 & 55462177 & 17 · 23 · 83 · 1709 \\ 18 & 8885251441 & 11 · 47 · 1109 · 15497 \\ 21 & 10585 & 5 · 29 · 73 \\ 22 & 2465 & 5 · 17 · 29 \\ 23 & 1105 & 5 · 13 · 17 \\ 25 & 11921001 & 3 · 29 · 263 · 521 \\ 31 & 62745 & 3 · 5 · 47 · 89 \\ 37 & 11972017 & 43 · 433 · 643 \\ 37 & 67902031 & 43 · 271 · 5827 \\ 39 & 334153 & 19 · 43 · 409 \\ 43 & 52633 & 7 · 73 · 103 \\ 44 & 15841 & 7 · 31 · 73 \\ 45 & 8911 & 7 · 19 · 67 \\ 47 & 2821 & 7 · 13 · 31 \\ 48 & 1729 & 7 · 13 · 19 \\ 49 & 1208361237478669 & 53 · 653 · 26479 · 1318579 \\ 50 & 4199932801 & 29 · 499 · 503 · 577 \\ 52 & 206955841 & 17 · 71 · 277 · 619 \\ 53 & 1271325841 & 17 · 31 · 179 · 13477 \\ 54 & 4169867689 & 13 · 29 · 383 · 28879 \\ 55 & 271794601 & 13 · 19 · 743 · 1481 \\ 60 & 6840001 & 7 · 17 · 229 · 251 \\ 61 & 1962804565 & 5 · 103 · 149 · 25579 \\ 67 & 11985924995083901 & 29 · 101 · 1427 · 16349 · 175403 \\ 67 & 410041 & 41 · 73 · 137 \\ 70 & 162401 & 17 · 41 · 233 \\ 76 & 4752717761 & 11 · 17 · 107 · 173 · 1373 \\ 81 & 35575075809505 & 5 · 197 · 223 · 353 · 458807 \\ 82 & 1496405933740345 & 5 · 47 · 317 · 40253 · 499027 \\ 83 & 142159958924185 & 5 · 37 · 107 · 58379 · 123017 \\ 83 & 158664761899885 & 5 · 37 · 107 · 53987 · 148469 \\ 83 & 204370370140285 & 5 · 37 · 107 · 48677 · 212099 \\ 83 & 24831908105124205 & 5 · 29 · 719 · 3023 · 78790717 \\ 92 & 520178982961 & 11 · 29 · 131 · 607 · 20507 \\ 94 & 12782849065 & 5 · 7 · 269 · 317 · 4283 \\ 95 & 8956911601 & 11 · 17 · 127 · 131 · 2879 \\ 97 & 5472940991761 & 199 · 241 · 863 · 132233 \\ 97 & 721574219707441 & 167 · 241 · 5039 · 3557977 \\ 97 & 83565865434172201 & 103 · 1993 · 9551 · 42622169 \\ 97 & 9729822470631481 & 127 · 409 · 110681 · 1692407 \\ 99 & 438253965870337 & 43 · 139 · 49409 · 1484009 \end{matrix}

Table 8. Carmichael numbers with small index

THE CARMICHAEL NUMBERS UP TO 10^{17} 9

\begin{matrix}ℓ & N & factors \\ 2.00163 & 3852971941960065 & 3 · 5 · 23 · 89 · 113 · 1409 · 788129 \\ 2.00388 & 655510549443465 & 3 · 5 · 23 · 53 · 389 · 2663 · 34607 \\ 2.00837 & 13462627333098945 & 3 · 5 · 23 · 53 · 197 · 8009 · 466649 \\ 2.01001 & 26708253318968145 & 3 · 5 · 17 · 113 · 57839 · 16025297 \\ 2.03067 & 269040992399565 & 3 · 5 · 23 · 29 · 4637 · 5799149 \\ 2.03207 & 158353658932305 & 3 · 5 · 17 · 89 · 149 · 563 · 83177 \\ 2.03614 & 1817671359979245 & 3 · 5 · 23 · 29 · 359 · 11027 · 45893 \\ 2.07138 & 16057190782234785 & 3 · 5 · 17 · 29 · 269 · 6089 · 1325663 \\ 2.07294 & 75131642415974145 & 3 · 5 · 23 · 29 · 53 · 617 · 9857 · 23297 \\ 2.08129 & 881715504450705 & 3 · 5 · 17 · 47 · 89 · 113 · 503 · 14543 \\ 2.08381 & 31454143858820145 & 3 · 5 · 17 · 23 · 2129 · 39293 · 64109 \\ 2.08894 & 6128613921672705 & 3 · 5 · 17 · 23 · 353 · 7673 · 385793 \\ 2.09841 & 12301576752408945 & 3 · 5 · 23 · 29 · 53 · 113 · 197 · 1042133 \\ 2.11432 & 1886616373665 & 3 · 5 · 17 · 23 · 83 · 353 · 10979 \\ 2.11493 & 3193231538989185 & 3 · 5 · 17 · 23 · 113 · 167 · 2927 · 9857 \\ 2.13936 & 11947816523586945 & 3 · 5 · 17 · 23 · 89 · 113 · 233 · 617 · 1409 \end{matrix}

Table 9. Carmichael numbers with Lehmer index greater than 2

References

[1] Jean-Marie De Koninck and Claude Levesque (eds.), Number theory: proceedings of the international number theory conference, Université de Laval, 1987, Berlin, Walter de Gruyter, 1989.

[2] Richard K. Guy, Unsolved problems in number theory, second ed., Unsolved problems in intuitive mathematics, vol. 1, Springer–Verlag, New York, 1994.

[3] 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.

[4] Richard G.E. Pinch, The Carmichael numbers up to 10^{15}, Math. Comp. 61 (1993), 381–391, Lehmer memorial issue.

[5] , The Carmichael numbers up to 10^{16}, March 1998, arXiv:math.NT/9803082.

[6] C. Pomerance, J.L. Selfridge, and S.S. Wagstaff jr, The pseudoprimes up to 25.10^{9}, Math. Comp. 35 (1980), no. 151, 1003–1026.

[7] Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587–593.

[8] , Two methods in elementary analytic number theory, in Mollin [3], Proceedings of the NATO Advanced Study Institute on Number Theory and Applications, pp. 136–161.

[9] Lawrence Somer, On Fermat d-pseudoprimes, in De Koninck and Levesque [1], pp. 841–860.

[10] J.D. Swift, Review 13[9] — table of Carmichael numbers to 10^{9}, Math. Comp. 29 (1975), 338–339.

2 Eldon Road, Cheltenham, Glos GL52 6TU, U.K.

  E-mail address: rgep@chalcedon.demon.co.uk