A338998 Composite numbers k such that phi(k) divides p*(k - 1) for some prime factor p of k - 1.

1729, 12801, 5079361, 34479361, 3069196417, 23915494401

Offset: 1

Author

Tomohiro Yamada, Nov 18 2020

Keywords

• nonn
• more

Comments

All terms of this sequence are terms of A337316 and all Lehmer numbers (if there are any) are contained in this sequence.

Terms 1729 and 3069196417 and several others are also Carmichael numbers (A002997), they are given in A339878.

The sequence also includes: 1334063001601, 6767608320001, 33812972024833, 380655711289345, 1584348087168001, 1602991137369601, 6166793784729601, 1531757211193440001. - Daniel Suteu, Nov 24 2020

Apparently, a(n) == 1 (mod 64). - Hugo Pfoertner, Dec 08 2020

The "Lehmer numbers" above refers to composite 1-Lehmer numbers, that is, numbers n that would satisfy the equation y * phi(n) = n-1, for some integer y > 1. Lehmer conjectured that no such numbers exist. See the assorted Web-links. - Antti Karttunen, Dec 26 2020

Examples

			phi(1729) = 1296 divides 3 * 1728.
		

Links

• D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.
• Giovanni Resta, k-Lehmer numbers
• Eric Weisstein's World of Mathematics, Lehmer's Totient Problem
• Wikipedia, Lehmer's totient problem

Crossrefs

Subsequence of A173703 (2-Lehmer numbers).

Cf. A337316 (with "squarefree divisor" instead of "prime factor").

Cf. A000010 (phi), A238574 (k-Lehmer numbers for some k), A339878 (Carmichael numbers in this sequence).

Programs

PARI

is(n)={my(s=denominator((n-1)/eulerphi(n))); !isprime(n) && isprime(s) && ((n-1)%s==0) && n>1}
{ forcomposite(n=1, 2^32, if(is(n), print1(n, ", "))) }

Extensions

a(5) from Amiram Eldar, Nov 18 2020

a(6) from Daniel Suteu, confirmed by Max Alekseyev, Sep 29 2023