A339909 Carmichael numbers k for which bigomega(phi(k)) < bigomega(k-1), where bigomega gives the number of prime divisors, counted with multiplicity.

1729, 14676481, 84350561, 90698401, 279377281, 382536001, 413138881, 542497201, 702683101, 781347841, 851703301, 939947009, 955134181, 3480174001, 4765950001, 5255104513, 5781222721, 5985964801, 7558388641, 7816642561, 8714965001, 9237473281, 13630072501, 18189007201, 21669076801, 21863001601, 23915494401, 25477682491

Offset: 1

Author

Antti Karttunen, Dec 22 2020

Keywords

• nonn

Comments

Natural numbers n that satisfy equation k * phi(n) = n - 1, for some integer k > 1, should all occur in this sequence, if they exist at all. Lehmer conjectured that there are no such numbers.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (calculated using data from Claude Goutier)
• Claude Goutier, Compressed text file carm10e22.gz containing all the Carmichael numbers up to 10^22.
• D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
• Wikipedia, Lehmer's totient problem.
• Index entries for sequences related to Carmichael numbers.

Crossrefs

Intersection of A002997 and A339908.

Cf. A000010, A001222, A002322.

Cf. also A339818, A339869, A339878.

Programs

Mathematica

carmichaels = Cases[Import["https://oeis.org/A002997/b002997.txt", "Table"], {, }][[;; , 2]]; Select[carmichaels, PrimeOmega[EulerPhi[#]] < PrimeOmega[# - 1] &] (* Amiram Eldar, Dec 26 2020 *)

PARI

A002322(n) = lcm(znstar(n)[2]); \\ From A002322
isA339909(n) = ((n>1)&&issquarefree(n)&&!isprime(n)&&(bigomega(eulerphi(n))A002322(n))));