login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 3-smooth 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 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

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

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 3|n. - 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 !! (n-1)

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 23:09 EST 2021. Contains 340249 sequences. (Running on oeis4.)