A113808 Positive integers n such that S(n) divides n, where S(n) is the sum of the iterates of the Euler phi-function of n, that is, S(n) = phi(n)+phi(phi(n))+....+ 1.

1, 2, 3, 6, 9, 15, 18, 27, 30, 39, 54, 78, 81, 111, 162, 183, 222, 243, 255, 327, 363, 366, 471, 486, 510, 654, 726, 729, 942, 1458, 2187, 2199, 3063, 4359, 4374, 4375, 4398, 5571, 6126, 6561, 8718, 8750, 8751, 11142, 13122, 15723, 17502, 19683, 31446, 36759

Offset: 1

Author

Jeffrey Shallit, Jan 22 2006

Keywords

• nonn

Examples

			18 is in the sequence because phi(18)+phi(phi(18))+phi(phi(phi(18))) = 6 + 2 + 1 = 9, which divides 18.
		

Links

• Donovan Johnson, Table of n, a(n) for n = 1..100
• Igor E. Shparlinski, On the sum of iterations of the Euler function, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.6.

Crossrefs

Cf. A092693, A082897.

Programs

Mathematica

s[1]=1; s[n_] := Total@NestWhileList[EulerPhi, n, #>1 &] - n; Select[Range@ 1000, Mod[#, s@#] == 0 &] (* Giovanni Resta, May 25 2013 *)

PARI

lista(nn) = {for (n=1, nn, s = 0; m = n; until (m == 1, m = eulerphi(m); s += m;); if ((n % s == 0), print1(n, ", ")););} \\ Michel Marcus, May 25 2013