

A007694


Numbers k such that phi(k) divides k.
(Formerly M0992)


35



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

a(n) divides p^a(n)  1 for all primes p >= 5.  Benoit Cloitre, Mar 22 2002
Also n such that sum( d divides n, mu(d)/d) has numerator of 1.  Benoit Cloitre, Apr 15 2002
n is here if and only if phi(n) divides also cototient(n). On the other hand, cototient(n) divides phi(n) if and only if n is a prime or power of a prime.  Labos Elemer, May 03 2002
It follows that n/phi(n) = 2 if n is a power of 2 and equal to 3 if n is of the form 6*A003586.  Gary Detlefs, Jun 28 2011
1 and even 3smooth numbers, cf. A003586.
Numbers n such that n = (1+omega(n))*phi(n).  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 kth 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


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
Michael W. Ecker and Scott J. Beslin, Problem E3037, Amer. Math. Monthly, Vol. 93, No. 8 (1986), pp. 656657.
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).
Math Stack Exchange, Is there phi(n)/n = 6
Wacław Sierpiński, Elementary Theory of Numbers, Warszawa, 1964.


FORMULA

n/phi(n) is an integer if and only if n = 1 or n = 2^w * 3^u for w > 0 and u >= 0.
n/phi(n) = 3 if and only if phi(n)n and 3n.  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)


EXAMPLE

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.


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 *)


PROG

(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
(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
(Haskell)
a007694 n = a007694_list !! (n1)
a007694_list = 1 : filter even a003586_list
 Reinhard Zumkeller, Jan 06 2014
(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


CROSSREFS

Cf. A000010, A049237, A007694, A007947, A003557, A023200, A003586, A001221, A033950, A235353 (subsequence), A068997 (subsequence).
Sequence in context: A318782 A064527 A333978 * A322492 A332276 A317246
Adjacent sequences: A007691 A007692 A007693 * A007695 A007696 A007697


KEYWORD

nonn,nice,easy


AUTHOR

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


STATUS

approved



