A339869 Carmichael numbers k for which A053575(k) [the odd part of phi] divides k-1.

561, 1105, 2465, 6601, 8911, 10585, 46657, 62745, 162401, 410041, 449065, 5148001, 5632705, 6313681, 6840001, 7207201, 11119105, 11921001, 19683001, 21584305, 26719701, 41298985, 55462177, 64774081, 67371265, 79411201, 83966401, 87318001, 99861985, 100427041, 172290241, 189941761, 484662529, 790623289, 809883361

Offset: 1

Author

Antti Karttunen, Dec 22 2020

Keywords

• nonn

Comments

Lehmer conjectured that the equation k * phi(n) = n - 1 (with k integer) has no solutions for any composite n (i.e., when k > 1). If this sequence has no common terms with A339818, then the conjecture certainly holds.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..1150 (terms below 10^22 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 A339880.

Complement of A340092 in A002997.

Cf. A000010, A000265, A002322, A053575.

Cf. also A339818, A339878, A339909.

Programs

Mathematica

carmichaels = Cases[Import["https://oeis.org/A002997/b002997.txt", "Table"], {, }][[;; , 2]]; oddPart[n_] := n/2^IntegerExponent[n, 2]; q[n_] := Divisible[n - 1, oddPart[EulerPhi[n]]]; Select[carmichaels, q] (* Amiram Eldar, Dec 26 2020 *)

PARI

A000265(n) = (n>>valuation(n, 2));
A002322(n) = lcm(znstar(n)[2]);
isA339869(n) = ((n>1)&&!isprime(n)&&(!((n-1)%A002322(n)))&&!((n-1)%A000265(eulerphi(n))));