Editing Carmichael number (section)

== Properties ==

=== Factorizations ===
Carmichael numbers have at least three positive prime factors. The first Carmichael numbers with <math>k = 3, 4, 5, \ldots</math> prime factors are {{OEIS|id=A006931}}:

{| class="wikitable"
|-
! ''k'' !! &nbsp;
|-
| 3 || <math>561 = 3 \cdot 11 \cdot 17\,</math>
|-
| 4 || <math>41041 = 7 \cdot 11 \cdot 13 \cdot 41\,</math>
|-
| 5 || <math>825265 = 5 \cdot 7 \cdot 17 \cdot 19 \cdot 73\,</math>
|-
| 6 || <math>321197185 = 5 \cdot 19 \cdot 23 \cdot 29 \cdot 37 \cdot 137\,</math>
|-
| 7 || <math>5394826801 = 7 \cdot 13 \cdot 17 \cdot 23 \cdot 31 \cdot 67 \cdot 73\,</math>
|-
| 8 || <math>232250619601 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 31 \cdot 37 \cdot 73 \cdot 163\,</math>
|-
| 9 || <math>9746347772161 = 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 31 \cdot 37 \cdot 41 \cdot 641\,</math>
|}

The first Carmichael numbers with 4 prime factors are {{OEIS|id=A074379}}:

{| class="wikitable"
|-
! ''i'' !!&nbsp;
|-
| 1 || <math>41041 = 7 \cdot 11 \cdot 13 \cdot 41\,</math>
|-
| 2 || <math>62745 = 3 \cdot 5 \cdot 47 \cdot 89\,</math>
|-
| 3 || <math>63973 = 7 \cdot 13 \cdot 19 \cdot 37\,</math>
|-
| 4 || <math>75361 = 11 \cdot 13 \cdot 17 \cdot 31\,</math>
|-
| 5 || <math>101101 = 7 \cdot 11 \cdot 13 \cdot 101\,</math>
|-
| 6 || <math>126217 = 7 \cdot 13 \cdot 19 \cdot 73\,</math>
|-
| 7 || <math>172081 = 7 \cdot 13 \cdot 31 \cdot 61\,</math>
|-
| 8 || <math>188461 = 7 \cdot 13 \cdot 19 \cdot 109\,</math>
|-
| 9 || <math>278545 = 5 \cdot 17 \cdot 29 \cdot 113\,</math>
|-
| 10 || <math>340561 = 13 \cdot 17 \cdot 23 \cdot 67\,</math>
|}

The second Carmichael number (1105) can be expressed as the sum of two squares in more ways than any smaller number. The third Carmichael number (1729) is the [[1729 (number)|Hardy-Ramanujan Number]]: the smallest number that can be expressed as the [[sum of two cubes]] (of positive numbers) in two different ways.

=== Distribution ===

Let <math>C(X)</math> denote the number of Carmichael numbers less than or equal to {{tmath|1= X }}. The distribution of Carmichael numbers by powers of 10 {{OEIS|id=A055553}}:<ref name="Pinch2007"/>

{| class="wikitable" style="margin:1em auto;"
|-
! <math>n</math>
|  1
|  2
|  3
|  4
|  5
|  6
|  7
|  8
|  9
| 10
| 11
| 12
| 13
| 14
| 15
| 16
| 17
| 18
| 19
| 20
| 21
|-
! <math>C(10^n)</math>
|        0
|        0
|        1
|        7
|       16
|       43
|      105
|      255
|      646
|     1547
|     3605
|     8241
|    19279
|    44706
|   105212
|   246683
|   585355
|  1401644
|  3381806
|  8220777
| 20138200
|}
In 1953, [[Walter Knödel|Knödel]] proved the [[Upper and lower bounds|upper bound]]:
: <math>C(X) < X \exp\left({-k_1 \left( \log X \log \log X\right)^\frac{1}{2}}\right)</math>
for some constant {{tmath|1= k_1 }}.

In 1956, Erdős improved the bound to
: <math>C(X) < X \exp\left(\frac{-k_2 \log X \log \log \log X}{\log \log X}\right)</math>
for some constant {{tmath|1= k_2 }}.<ref name="Erdős1956">{{cite journal |author=Erdős, P. |year=2022 |title=On pseudoprimes and Carmichael numbers |journal=Publ. Math. Debrecen |volume=4 |issue=3–4 |pages=201–206 |doi=10.5486/PMD.1956.4.3-4.16 |url=http://www.renyi.hu/~p_erdos/1956-10.pdf |archive-url=https://web.archive.org/web/20110611160632/http://www.renyi.hu/~p_erdos/1956-10.pdf |archive-date=2011-06-11 |url-status=live |mr=79031 |s2cid=253789521 |author-link=Paul Erdős }}</ref> He further gave a [[heuristic argument]] suggesting that this upper bound should be close to the true growth rate of {{tmath|1= C(X) }}.

In the other direction, [[W. R. (Red) Alford|Alford]], [[Andrew Granville|Granville]] and [[Carl Pomerance|Pomerance]] proved in 1994<ref name="Alford-1994" /> that for [[Eventually (mathematics)|sufficiently large]] ''X'',
: <math>C(X) > X^\frac{2}{7}.</math>

In 2005, this bound was further improved by [[Glyn Harman|Harman]]<ref>{{cite journal |author=Glyn Harman |title=On the number of Carmichael numbers up to ''x'' |journal=Bulletin of the London Mathematical Society |volume=37 |issue=5 |year=2005 |pages=641–650 |doi=10.1112/S0024609305004686|s2cid=124405969 }}</ref> to
: <math>C(X) > X^{0.332}</math>
who subsequently improved the exponent to {{tmath|1= 0.7039 \cdot 0.4736 = 0.33336704 > 1/3 }}.<ref>
{{cite journal |last=Harman |first=Glyn
 |date=2008 |title=Watt's mean value theorem and Carmichael numbers
 |doi=10.1142/S1793042108001316 |mr=2404800
 |journal=International Journal of Number Theory |volume=4 |issue=2 |pages=241–248
}}</ref>

Regarding the asymptotic distribution of Carmichael numbers, there have been several conjectures. In 1956, Erdős<ref name="Erdős1956"/> conjectured that there were <math>X^{1-o(1)}</math> Carmichael numbers for ''X'' sufficiently large. In 1981, Pomerance<ref name="Pomerance1981">{{cite journal |author=Pomerance, C. |year=1981 |title=On the distribution of pseudoprimes |journal=Math. Comp. |volume=37 |issue=156 |pages=587–593|jstor=2007448 |doi=10.1090/s0025-5718-1981-0628717-0|author-link=Carl Pomerance |doi-access=free }}</ref> sharpened Erdős' heuristic arguments to conjecture that there are at least
: <math> X \cdot L(X)^{-1 + o(1)} </math>
Carmichael numbers up to {{tmath|1= X }}, where {{tmath|1= L(x) = \exp{ \left( \frac{\log x \log\log\log x} {\log\log x} \right) } }}.

However, inside current computational ranges (such as the count of Carmichael numbers performed by Goutier{{OEIS|id=A055553}} up to 10<sup>22</sup>), these conjectures are not yet borne out by the data; empirically, the exponent is <math> C(X) \approx X^{0.35}</math> for the highest available count (C(X)=49679870 for X= 10<sup>22</sup>).

<!-- Too indirect and long? -->In 2021, [[Daniel Larsen (mathematician)|Daniel Larsen]] proved an analogue of [[Bertrand's postulate]] for Carmichael numbers first conjectured by Alford, Granville, and Pomerance in 1994.<ref name="Cepelewicz-2022" /><ref>{{cite journal |author=Larsen, Daniel |date=20 July 2022 |title=Bertrand's Postulate for Carmichael Numbers |url=https://academic.oup.com/imrn/advance-article-abstract/doi/10.1093/imrn/rnac203/6647493 |journal=International Mathematics Research Notices |volume=2023 |issue=15 |pages=13072–13098 |arxiv=2111.06963 |doi=10.1093/imrn/rnac203}}</ref> Using techniques developed by [[Yitang Zhang]] and [[James Maynard (mathematician)|James Maynard]] to establish results concerning [[Twin prime conjecture|small gaps between primes]], his work yielded the much stronger statement that, for any <math>\delta>0</math> and sufficiently large <math>x</math> in terms of <math>\delta</math>, there will always be at least  
: <math>\exp{\left(\frac{\log{x}}{(\log \log{x})^{2+\delta}}\right)} </math>
Carmichael numbers between <math>x</math> and
: <math>x+\frac{x}{(\log{x})^{\frac{1}{2+\delta}}}.</math>