A068997 -id:A068997 - cp's OEIS frontend

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

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

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

			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.

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

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.

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

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

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

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

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

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

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

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

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)

A304407 If n = Product (p_j^k_j) then a(n) = Product ((p_j - 1)*k_j).

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 3, 4, 4, 10, 4, 12, 6, 8, 4, 16, 4, 18, 8, 12, 10, 22, 6, 8, 12, 6, 12, 28, 8, 30, 5, 20, 16, 24, 8, 36, 18, 24, 12, 40, 12, 42, 20, 16, 22, 46, 8, 12, 8, 32, 24, 52, 6, 40, 18, 36, 28, 58, 16, 60, 30, 24, 6, 48, 20, 66, 32, 44, 24, 70, 12, 72, 36, 16

Offset: 1

Ilya Gutkovskiy, May 12 2018

			a(60) = a(2^2*3*5) = (2 - 1)*2 * (3 - 1)*1 * (5 - 1)*1 = 16.

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Ilya Gutkovskiy, Scatter plot of a(n) up to n=50000.
Index entries for sequences computed from exponents in factorization of n.
Index entries for sequences computed from indices in prime factorization.

Cf. A000010, A000026, A000040, A002110, A003958, A005117, A005361, A005867, A006093, A007947, A023900, A048250, A059975, A068997, A081294 (numbers n such that a(n) is odd), A087656, A090624, A152649, A173557, A304117, A304408, A304409, A304411, A304412.

Cf. A001221, A076479.

seq(mul((p-1)*padic[ordp](n, p), p in numtheory[factorset](n)), n=1..100); # Ridouane Oudra, Jun 06 2025

a[n_] := Times @@ ((#[[1]] - 1) #[[2]] & /@ FactorInteger[n]); a[1] = 1; Table[a[n], {n, 75}]
Table[EulerPhi[Last[Select[Divisors[n], SquareFreeQ]]] DivisorSigma[0, n/Last[Select[Divisors[n], SquareFreeQ]]], {n, 75}]

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); (p-1)*e)} \\ Andrew Howroyd, Jul 24 2018

a(n) = A005361(n)*abs(A023900(n)) = A005361(n)*A173557(n) = A005361(n)*A000010(A007947(n)).
a(p^k) = (p - 1)*k where p is a prime and k > 0.
a(n) = phi(n) if n is a squarefree (A005117), where phi() = A000010.
a(A002110(k)) = A005867(k).
Sum_{k=1..n} a(k) ~ c * n^2, where c = (Pi^4/72) * Product_{p prime} (1 - 4/p^2 + 3/p^3 + 1/p^4 - 1/p^5) = 0.2644703894... . - Amiram Eldar, Nov 30 2022
a(n) = (-1)^A001221(n) * (Sum_{d1|n} Sum_{d2|n} mu(d1)*gcd(d1,d2)). - Ridouane Oudra, Jun 06 2025

A293928 Totients phi(m) having one or more solutions m to phi(m)^2 = phi(phi(m)*m).

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 48, 54, 64, 72, 80, 84, 96, 100, 108, 120, 128, 144, 160, 162, 168, 192, 200, 216, 240, 252, 256, 272, 288, 312, 320, 324, 336, 360, 384, 400, 432, 440, 480, 486, 500, 504, 512, 544, 576, 588, 600, 624, 640, 648, 672, 684

Offset: 1

Torlach Rush, Oct 19 2017

nonn

"Totients" are terms of A000010. - N. J. A. Sloane, Oct 22 2017
The smallest totient absent from the list is 10. This is because the totient inverses of 10, 11 and 22 are not solutions to phi(m)^2 = phi(phi(m)*m).
The formula is recursive. For example, taking a(22) we get the following: 11664 = phi(108*324), 1259712 = phi(11664*324), 136048896 = phi(1259712*324), ...
Where (if ever) does this first differ from A068997? - R. J. Mathar, Oct 30 2017
Apparently the set of the m is A151999. - R. J. Mathar, Mar 25 2024
If m satisfies phi(m)^2 = phi(phi(m)*m), then it satisfies phi(m)^(k+1) = phi(phi(m)^k*m) for all k >= 1. - Max Alekseyev, Dec 03 2024

			96 is a term since 96^2 = phi(96*288), with m=288 where phi(288) = 96.

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A006511, A032447, A007366.

Subsequence of A002202.

isok(n) = {my(iv = invphi(n)); if (#iv, for (m = 1, #iv, if (n^2 == eulerphi(n*iv[m]), return (1)););); return (0);} \\ using the invphi script by Max Alekseyev; Michel Marcus, Nov 01 2017

More terms from Michel Marcus, Oct 24 2017

Definition simplified by Max Alekseyev, Dec 03 2024

A294618 a(n) is the number of solutions of x^2 = eulerphi(x * m) where x is A293928(n).

Original entry on oeis.org

2, 2, 3, 1, 4, 2, 5, 1, 1, 4, 6, 3, 3, 5, 1, 7, 6, 4, 1, 7, 1, 3, 1, 8, 10, 5, 1, 1, 9, 3, 8, 4, 1, 9, 1, 13, 1, 7, 4, 3, 1, 12, 5, 14, 1, 7, 1, 1, 2, 10, 2, 18, 1, 1, 1, 9, 9, 3, 1, 5, 1, 14, 7, 22, 3, 1

Offset: 1

Torlach Rush, Nov 05 2017

The valid values of m in the equation are the terms of the sequence A151999 in order.
m is a solution if all squarefree divisors of x also divide m.
The formula is recursive. For example, taking A151999(68) we get the following: 11664=phi(108*324), 1259712=phi(11664*324), 136048896=phi(1259712*324), ...
If a solution exists then x^(k+1) = phi(x^k * m) for a fixed m, and the smallest value of k must be 1. This follows from a|b implies phi(a)|phi(b), and for k >= 1 a^(k-1)|a^k.
The smallest solution where solutions exist are the terms of the sequence A055744 not in order.
The values of phi(m) are the terms of the sequence A068997 not in order.

			The first 1 is a term since there is only 1 solution when phi(m)=6. The solution is m=18.
The first 5 is a term since there are 5 solutions when phi(m)=16. These are 32, 34, 40, 48, and 60.
From _Michel Marcus_, Nov 08 2017: (Start)
Illustration of first few terms:
   1: [1, 2],
   2: [4, 6],
   4: [8, 10, 12],
   6: [18],
   8: [16, 20, 24, 30],
  12: [36, 42],
  16: [32, 34, 40, 48, 60],
  18: [54],
  20: [50],
  24: [72, 78, 84, 90],
  32: [64, 68, 80, 96, 102, 120],
  ... (End)

Max Alekseyev, PARI scripts for various problems

Cf. A000010, A006511, A032447, A151999, A055744, A068997, A293928.

isok(n) = {iv = invphi(n); if (#iv, return (sum(m=1, #iv, n^2 == eulerphi(n*iv[m])))); return (0);}
lista(nn) = {for (n=1, nn, if (v = isok(n), print1(v, ", ")););} \\ \\ using the invphi script by Max Alekseyev; Michel Marcus, Nov 07 2017

0 < (phi(m)^(k+1) = phi(phi(m)^k*m)), k >= 1, m >= 1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

R

Sage

Formula

A304407 If n = Product (p_j^k_j) then a(n) = Product ((p_j - 1)*k_j).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A293928 Totients phi(m) having one or more solutions m to phi(m)^2 = phi(phi(m)*m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A294618 a(n) is the number of solutions of x^2 = eulerphi(x * m) where x is A293928(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula