A007694 Numbers k such that phi(k) divides k.

1, 2, 4, 6, 8, 12, 16, 18, 24, 32, 36, 48, 54, 64, 72, 96, 108, 128, 144, 162, 192, 216, 256, 288, 324, 384, 432, 486, 512, 576, 648, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2304, 2592, 2916, 3072, 3456, 3888, 4096, 4374, 4608, 5184, 5832, 6144, 6912, 7776, 8192, 8748, 9216

Offset: 1

Author

N. J. A. Sloane, Robert G. Wilson v

Keywords

• nonn
• nice
• easy

Comments

a(n) divides p^a(n) - 1 for all primes p >= 5. - Benoit Cloitre, Mar 22 2002

Also k such that Sum_{d divides k} mu(d)/d has numerator 1. - Benoit Cloitre, Apr 15 2002

k is here if and only if phi(k) also divides cototient(k). On the other hand, cototient(k) divides phi(k) if and only if k is a prime or power of a prime. - Labos Elemer, May 03 2002

It follows that k/phi(k) = 2 if k is a power of 2 and equal to 3 if k is of the form 6*A003586. - Gary Detlefs, Jun 28 2011

1 and even 3-smooth numbers, cf. A003586. - Reinhard Zumkeller, Jan 06 2014

Numbers k such that k = (1+omega(k))*phi(k). - Farideh Firoozbakht, Oct 02 2014

These are the integers whose largest squarefree divisor is 1, 2 or 6. As such, this sequence is equal to the set V_infinite, defined as the intersection of the V_k for k >= 1, where V_k(x) = {phi_k(n) <= x} and phi_k is the k-th iterate of phi, the Euler function; for instance, V_1 is given by A002202 (see Theorem 7 in Pomerance and Luca). - Michel Marcus, Nov 09 2015

This sequence is contained in A068997. The terms of A068997 not in this sequence have largest squarefree divisor other than 1, 2, or 6, beginning with 10. - Torlach Rush, Dec 07 2017

Examples

			12 is in the sequence because 12/phi(12) = 12/4 = 3, which is an integer.
16 is in the sequence because 16/phi(16) = 16/8 = 2, which is an integer.
20 is not in the sequence because 20/phi(20) = 20/8 = 5/2 = 2.5, which is not an integer.
		

References

• J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique Des Nombres, Problem 526 pp. 71; 256, Ellipses Paris 2004.
• Sárközy A. and Suranyi J., Number Theory Problem Book (in Hungarian), Tankonyvkiado, Budapest, 1972.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Roohollah Ebrahimian, When Does phi(n) divide n? A Number Theory Math Competition Problem., YouTube video, 2023.
• Michael W. Ecker and Scott J. Beslin, Problem E3037, Amer. Math. Monthly, Vol. 93, No. 8 (1986), pp. 656-657.
• Florian Luca and Carl Pomerance, On the range of the iterated Euler function, Article 8, Integers: Electronic Journal of Combinatorial Number Theory, Proceedings of the Integers Conference 2007, Volume 9 Supplement (2009).
• Mathematics Stack Exchange, Is there phi(n)/n = 6
• Wacław Sierpiński, Elementary Theory of Numbers, Warszawa, 1964.

Crossrefs

Cf. A000010, A049237, A007694, A007947, A003557, A023200, A003586, A001221, A033950, A235353 (subsequence), A068997 (subsequence).

Programs

Haskell

a007694 n = a007694_list !! (n-1)
a007694_list = 1 : filter even a003586_list
-- Reinhard Zumkeller, Jan 06 2014

Maple

select(n -> n mod numtheory:-phi(n) = 0, [$1..5000]); # Robert Israel, Nov 03 2014

Mathematica

Select[ Range[5000], IntegerQ[ #/EulerPhi[ # ]] &]
m = 5000; Join[{1}, Sort @ Flatten @ Table[2^i*3^j, {i, 1, Log2[m]}, {j, 0, Log[3, m/2^i]}]] (* Amiram Eldar, Oct 29 2020 *)

PARI

for(n=1,10^6, if (n%eulerphi(n)==0,print1(n,", "))); \\ Joerg Arndt, Apr 04 2013

PARI

list(lim)=my(v=List([1]),t); for(i=1,logint(lim\1,2), listput(v,t=2^i); for(j=1,logint(lim\t,3), listput(v,t*=3))); Set(v) \\ Charles R Greathouse IV, Nov 10 2015

R

library(numbers); j=N=1
while(j<200) if(isNatural((N=N+1)/eulersPhi(N))) dtot[(j=j+1)]=N # Christian N. K. Anderson, Apr 04 2013

Sage

is_A007694 = lambda n: euler_phi(n).divides(n)
A007694_list = lambda len: filter(is_A007694, (1..len))
A007694_list(4100) # Peter Luschny, Oct 03 2014

Formula

k/phi(k) is an integer if and only if k = 1 or k = 2^w * 3^u for w > 0 and u >= 0.

k/phi(k) = 3 if and only if phi(k)|k and 3|k. - Thomas Ordowski, Nov 03 2014

a(n) is approximately exp(sqrt(2*log(2)*log(3)*n))/sqrt(3/2). - Charles R Greathouse IV, Nov 10 2015

From Amiram Eldar, Oct 29 2020: (Start)

a(n) = 2 * A003586(n) for n > 1.

Sum_{n>=1} 1/a(n) = 5/2. (End)