A203966 Numbers n such that phi(n) divides n+1, where phi is Euler's totient function (A000010).

1, 2, 3, 15, 255, 65535, 83623935, 4294967295, 6992962672132095

Offset: 1

Author

José María Grau Ribas, Jan 08 2012

Keywords

• nonn
• more

Comments

Numbers k such that A060473(k) = 1. - Robert G. Wilson v, Jul 06 2014

Except for a(2), all terms are odd. - Chai Wah Wu, Jun 06 2017

Since gcd(phi(n),n) = 1, all terms are squarefree. Then, for n = p1 * ... * pk with primes p1 < ... < pk, (n+1)/phi(n) is very close to p1/(p1-1)*...*pk/(p1-1). Since p/(p-1) is decreasing as p grows, having (n+1)/phi(n) = 3 implies that p1 >= 5 and further that n >= 2.4*10^56 is a product of at least 33 primes. Similarly, having (n+1)/phi(n) >= 4 implies that n >= 1.6*10^30 is a product of at least 21 primes. Hence, the terms of this sequence below 1.6*10^30 have (n+1)/phi(n) = 2 and thus coincide with A050474. - Max Alekseyev, Jan 30 2022

Examples

			15 is in the sequence because phi(15) = 8, and 8 divides 16 = 15 + 1 evenly.
		

Links

• D. H. Lehmer, On Euler's totient function, Bulletin of the American Mathematical Society, 38 (1932), 745-751.

Crossrefs

Cf. A060473, A000010, A202855.

Superset of A050474.

Programs

Mathematica

Select[Range[100000], Divisible[#+1, EulerPhi[#]]&]

Extensions

a(8) from Donovan Johnson, Jan 13 2012

a(9) confirmed by Max Alekseyev, Jan 30 2022