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,2

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

Links

Table of n, a(n) for n=1..9.

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

Example

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

Mathematica

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

Crossrefs

Cf. A060473, A000010, A202855.

Superset of A050474.

Sequence in context: A162108 A162100 A330871 * A250404 A167444 A292709

Adjacent sequences: A203963 A203964 A203965 * A203967 A203968 A203969

Keyword

nonn,more

Author

José María Grau Ribas, Jan 08 2012

Extensions

a(8) from Donovan Johnson, Jan 13 2012

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

Status

approved