login
3-Carmichael numbers: Carmichael numbers equal to the product of 3 primes: k = p*q*r, where p < q < r are primes such that a^(k-1) == 1 (mod k) if a is prime to k.
70

%I #37 Aug 04 2022 08:54:20

%S 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,46657,52633,

%T 115921,162401,252601,294409,314821,334153,399001,410041,488881,

%U 512461,530881,1024651,1152271,1193221,1461241,1615681,1857241,1909001,2508013

%N 3-Carmichael numbers: Carmichael numbers equal to the product of 3 primes: k = p*q*r, where p < q < r are primes such that a^(k-1) == 1 (mod k) if a is prime to k.

%C It is interesting that most of the numbers have the last digit 1. For example 530881, 3581761, 7207201, etc.

%C Granville & Pomerance conjecture that there are ~ c x^(1/3)/(log x)^3 terms of this sequence up to x. Heath-Brown proves that, for any e > 0, there are O(x^(7/20 + e)) terms of this sequence up to x. - _Charles R Greathouse IV_, Nov 19 2012

%C All 3-term Carmichael numbers can be represented by certain Chernick polynomials, whose values obey a strict s-decomposition (A324460) besides certain exceptions. Under Dickson's conjecture, "almost all" 3-term Carmichael numbers are primary Carmichael numbers (A324316) in the sense that C'_3(x)/C_3(x) -> 1 as x -> infinity, where C_3(x) counts the 3-term Carmichael numbers and C'_3(x) counts the 3-term primary Carmichael numbers up to x. A primary Carmichael number m has the unique property (*) that for each prime divisor p of m, the sum of the base-p digits of m equals p. As a nontrivial result, all 3-term Carmichael numbers m have at least the property that (*) holds for the greatest prime divisor p of m, see Kellner 2019. - _Bernd C. Kellner_, Aug 03 2022

%D O. Ore, Number Theory and Its History, McGraw-Hill, 1948, Reprinted by Dover Publications, 1988, Chapter 14.

%H R. J. Mathar and Charles R Greathouse IV, <a href="/A087788/b087788.txt">Table of n, a(n) for n = 1..10000</a> (first 3284 terms from Mathar)

%H F. Arnault, <a href="http://dx.doi.org/10.1006/jsco.1995.1042">Constructing Carmichael numbers which are strong pseudoprimes to several bases</a>, Journal of Symbolic Computation, vol. 20, no 2, Aug. 1995, pp. 151-161.

%H Jack Chernick, <a href="http://projecteuclid.org/euclid.bams/1183501763">On Fermat's simple theorem</a>, Bull. Amer. Math. Soc., Vol. 45, No. 4 (1939), pp. 269-274.

%H Harvey Dubner, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Dubner/dubner6.html">Carmichael Numbers of the form (6m+1)(12m+1)(18m+1)</a>, Journal of Integer Sequences, Vol. 5 (2002) Article 02.2.1,

%H A. Granville and C. Pomerance, <a href="http://dx.doi.org/10.1090/S0025-5718-01-01355-2">Two contradictory conjectures concerning Carmichael numbers</a>, Math. Comp. 71 (2002), pp. 883-90.

%H D. R. Heath-Brown, <a href="http://eprints.maths.ox.ac.uk/680/1/carmichael.pdf">Carmichael numbers with three prime factors</a>, Hardy-Ramanujan Journal 30 (2007), pp. 6-12.

%H G. Jaeschke, <a href="http://dx.doi.org/10.1090/S0025-5718-1990-1023763-5">The Carmichael numbers to 10^12</a>, Math. Comp., 55 (1990), 383-389.

%H Bernd C. Kellner and Jonathan Sondow, <a href="http://math.colgate.edu/~integers/v52/v52.pdf">On Carmichael and polygonal numbers, Bernoulli polynomials, and sums of base-p digits</a>, Integers 21 (2021), #A52, 21 pp.; arXiv:<a href="https://arxiv.org/abs/1902.10672">1902.10672</a> [math.NT], 2019.

%H Bernd C. Kellner, <a href="http://math.colgate.edu/~integers/w38/w38.pdf">On primary Carmichael numbers</a>, Integers 22 (2022), #A38, 39 pp.; arXiv:<a href="https://arxiv.org/abs/1902.11283">1902.11283</a> [math.NT], 2019.

%H Math Reference Project, <a href="http://www.mathreference.com/num-mod,ccm.html">Carmichael Numbers</a>

%H R. G. E. Pinch, <a href="http://www.s369624816.websitehome.co.uk/rgep/cartable.html">The Carmichael numbers up to 10^18</a>, 2008.

%H Rosetta Code, <a href="http://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes">Programs for finding 3-Carmichael numbers</a>

%F k is composite and squarefree and for p prime, p|k => p-1|k-1. A composite odd number k is a Carmichael number if and only if k is squarefree and p-1 divides k-1 for every prime p dividing k (Korselt, 1899) k = p*q*r, p-1|k-1, q-1|k-1, r-1|k-1.

%e a(6)=6601=7*23*41: 7-1|6601-1, 23-1|6601-1, 41-1|6601-1, i.e., 6|6600, 22|6600, 40|6600.

%o (PARI) list(lim)=my(v=List());forprime(p=3,(lim)^(1/3), forprime(q=p+1, sqrt(lim\p),forprime(r=q+1,lim\(p*q),if((q*r-1)%(p-1)||(p*r-1)%(q-1)||(p*q-1)%(r-1),,listput(v,p*q*r)))));vecsort(Vec(v)) \\ _Charles R Greathouse IV_, Nov 19 2012

%Y Cf. A002997, A162290.

%K easy,nonn

%O 1,1

%A _Miklos Kristof_, Oct 07 2003

%E Minor edit to definition by _N. J. A. Sloane_, Sep 14 2009