A049237 -id:A049237 - 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)

A055458 a(n) = smallest composite solution x to the equation phi(x+2n) = phi(x)+2n.

Original entry on oeis.org

6, 12, 21, 24, 36, 45, 48, 39, 63, 72, 72, 95, 60, 57, 224, 84, 15, 135, 1058, 45, 301, 144

Offset: 1

Labos Elemer, Jun 26 2000

Sivaramakrishnan (1989) quotes Makowski, who gave solutions for phi(x+d) = phi(x)+d with d = 2^a and d = 2*3^a. Compare also A007694 and A049237.
Smallest prime solutions appear to be identical with A054906.
a(23) is presently unknown.
The sequence continues as (with ? for unknown values): ?, 95, 162, 63, 189, 69, 156, 161, 180, 69, 260, 150, ?, 115, 204, 129, 400, 75, 180, 165, 35, 117, 476, 7105, 288, 195, ?, 324, 620, 240, 81, 145, 14531, 153, 644, 309, ?, 203, ?, 63, 640, 75, 372, 285, 2312, 33, 343, 642, 336, 155, ?, 147, 728, 396, 1564, 185, 564, 87, 567, 360, 360, 155, 492, 510, 560, 516, 516, 301, 4232, 261, 860, 387, 576, 185, 564, 309, 1000, 225 ... - Don Reble, Apr 29 2015

			a(19) = 1058 because phi(1058 + 38) = phi(1096) = 544 = 506 + 38 = phi(1058) + 38.
a(100) = 225, phi(225 + 200) = phi(425) = 320 = 120 + 200 = phi(225) + 200.

Sivaramakrishnan, R. (1989): Classical theory of Arithmetical Functions. Marcel Dekker, Inc., New York-Basel. Chapter V, Problem 20, page 113.

Cf. A000010, A054906, A050472, A050473, A007694, A049237.

A055458 := proc(n)
    local x;
    for x from 0 do
        if not isprime(x) then
        if numtheory[phi](x+2*n) = numtheory[phi](x)+2*n then
            return x;
        end if;
        end if;
    end do:
end proc: # R. J. Mathar, Sep 23 2016

Table[k = 4; While[Nand[CompositeQ@ k, EulerPhi[k + 2 n] == EulerPhi[k] + 2 n], k++]; k, {n, 22}] (* Michael De Vlieger, Dec 17 2016 *)

a(n)=forcomposite(x=4,, if(eulerphi(x+2*n) == eulerphi(x)+2*n, return(x))) \\ does not handle -1s; Charles R Greathouse IV, Apr 28 2015

More terms from Michel ten Voorde Jun 14 2003

Entry revised by N. J. A. Sloane, Apr 28 2015

A086411 Greatest prime factor of 3-smooth numbers.

Original entry on oeis.org

1, 2, 3, 2, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 3, 3, 3, 3

Offset: 1

Reinhard Zumkeller, Jul 18 2003

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A003586, A006530, A006899, A033845, A086410.

Reap[Do[p = FactorInteger[n][[-1, 1]]; If[p < 5, Sow[p]], {n, 1, 2*10^5}] ][[2, 1]] (* Jean-François Alcover, Dec 17 2017 *)

a(n) = A006530(A003586(n)).
A086410(n) <= a(n) <= 3.
a(A033845(n)) = A086410(A033845(n))+1; a(A006899(n)) = A086410(A006899(n)). - Reinhard Zumkeller, Sep 25 2008
Conjecture: a(n) = A049237(n+1) for n>1. - R. J. Mathar, Jun 06 2024

A062356 a(n) = floor(n/phi(n)).

Original entry on oeis.org

1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 2

Offset: 1

Jason Earls, Jul 07 2001

Reference does not include the floor function.

See A007694 for the numbers for which n/phi(n) is an integer, and A049237 for the ratios.

D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc. Boston MA, 1976, Prob. 7-4 3, p. 152.

Harry J. Smith, Table of n, a(n) for n=1,...,2000

Cf. A000010, A007694, A049237.

Table[Floor[n/EulerPhi@ n], {n, 120}] (* Michael De Vlieger, Jul 02 2016 *)

(a(n)=n\eulerphi(n)); vector(250,n,a(n)) \\ Edited by M. F. Hasler, Jul 02 2016

{ for (n=1, 2000, write("b062356.txt", n, " ", floor(n/eulerphi(n))) ) } \\ Harry J. Smith, Aug 05 2009; irrelevant realprecision(...) deleted by M. F. Hasler, Jul 02 2016

From M. F. Hasler, Jul 02 2016: (Start)
A062356(n = 2k+1) = 1 except for n in A036798.
A062356(n = 6k+2) = 2 except for n in 70*{11, 17, 23, 26, 29, 38, 44, 62, 65, 68, 77, 92, 95, 104, 110, ...} or n in 10*{2717, 4199, 4301, 4433, 4862, 5291, 5423, 6149, 6578, 7106, 8294, 8723, 9581, 9614, ...} or n = 646646, 874874, ....
A062356(n = 6k+4) = 2 except for n in 70*{13, 19, 22, 31, 34, 46, 52, 55, 58, 76, 85, 88, 91, 115, 121, ...} or n in 10*{2431, 3289, 3553, 4147, 4807, 5083, 5434, 5797, 5863, 6061, 6721, 6919, 7579, 8398, 8437, 8602, 8866, 9724, ...} or n = 782782, 986986, ....
A062356(n = 6k) = 3 except for n in 30*{7, 11, 13, 14, 21, 22, 26, 28, 33, 35, 39, 42, 44, 49, 52, 55, 56, 63, 65, 66, 70, 77, 78, 84, 88, 91, 98, 99, ...} or n in 42*{143, 187, 209, 221, 247, 253, 286, 374, 418, 429, 442, 494, 506, 561, 572, 627, 663, 741, 748, 759, 836, 858, 884,...} or n = 277134, 554268, 831402, .... (End)

A063872 Let m be the n-th positive integer such that phi(m) is divisible by m - phi(m). Then a(n) = phi(m)/(m - phi(m)).

Original entry on oeis.org

1, 2, 1, 4, 6, 1, 2, 10, 12, 1, 16, 18, 22, 4, 2, 28, 30, 1, 36, 40, 42, 46, 6, 52, 58, 60, 1, 66, 70, 72, 78, 2, 82, 88, 96, 100, 102, 106, 108, 112, 10, 4, 126, 1, 130, 136, 138, 148, 150, 156, 162, 166, 12, 172, 178, 180, 190, 192, 196, 198, 210, 222, 226, 228, 232

Offset: 1

Labos Elemer, Aug 27 2001

m is the n-th prime power larger than 1; i.e., m = A000961(n+1). Proof: If phi(m) is divisible by m-phi(m), then m is divisible by m-phi(m). Let k be the product of the distinct prime factors of m. Then phi(m)/m = phi(k)/k, so k/(k-phi(k)) = m/(m-phi(m)) is an integer. Thus k is divisible by k-phi(k) and k is squarefree. Let k-phi(k) = d and k/(k-phi(k)) = e; note that e>1 and GCD(d,e)=1. Thus d = k - phi(k) = d e - phi(d e) = d e - phi(d) phi(e) so d (e-1) = d e - d = phi(d) phi(e) <= phi(d) (e-1) and d <= phi(d). But this implies that d=1, so phi(k)=k-1 and k is prime. Hence m is a prime power. - Dean Hickerson, Aug 28 2001
For primes, quotient = (p - 1) / 1 = p - 1; for prime powers, p^a, a > 1: quotient = p^(a - 1)(p - 1) / p^(a - 1) = p - 1, so each p - 1 values occur infinitely often: a(n) + 1 = root of n-th prime power with positive exponent, i.e., A025473(n+1). - [Edited by] Daniel Forgues, May 08 2014
"LCM numeral system": a(n+1) is maximum digit for index n, n >= 0; a(-n) is maximum digit for index n, n < 0. - Daniel Forgues, May 03 2014

Harvey P. Dale, Table of n, a(n) for n = 1..1000
OEIS Wiki, LCM numeral system

Cf. A000010, A051953, A007694, A000961, A054740, A049237, A025473.

epd[n_]:=Module[{ep=EulerPhi[n]},If[Divisible[ep,n-ep],ep/(n-ep),Nothing]]; Array[epd,300,2] (* Harvey P. Dale, Dec 27 2020 *)

M(n) = ispower(n, , &n); if (isprime(n), n, 1); \\ A014963
apply(x->x-1, select(isprime, apply(x->M(x+1), [1..260]))) \\ Michel Marcus, Sep 14 2021

a(n) = A025473(n + 1) - 1. - Bill McEachen, Sep 11 2021

A054740 Cototient(n)/totient(n) when this is an integer.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 1

Labos Elemer, Apr 26 2000

nonn

EulerPhi of x divides x (A007694) if and only if EulerPhi divides x-EulerPhi. This quotient is smaller by 1 than A049237.

			x=2592, Phi[2592]=864, Cototient[x]=2592-864=1728 and the quotients are as follows: x/Phi=2592/864=3 or Cototient[x]/Phi[x]=1728/864=2; x always has a form of 2^u*3^w

Sárközy A. and Suranyi J., Number Theory Problem Book (in Hungarian)

A000010, A049237, A007694, A051953.

Select[(#-EulerPhi[#])/EulerPhi[#]&/@Range[300000],IntegerQ] (* Harvey P. Dale, Mar 01 2015 *)

A051953[A007694(n)]/A000010[A007694(n)] = A049237(n)-1

A063755 Squares k which are divisible by phi(k).

Original entry on oeis.org

1, 4, 16, 36, 64, 144, 256, 324, 576, 1024, 1296, 2304, 2916, 4096, 5184, 9216, 11664, 16384, 20736, 26244, 36864, 46656, 65536, 82944, 104976, 147456, 186624, 236196, 262144, 331776, 419904, 589824, 746496, 944784, 1048576, 1327104

Offset: 1

Jason Earls, Aug 14 2001

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..160 from Harry J. Smith)

Cf. A000010, A000290, A049237, A007694. Squares arising in A007694.

Select[ Range[ 1, 2000 ], Mod[ #^2, EulerPhi[ #^2 ] ]==0& ]^2
Select[Range[2000]^2,Divisible[#,EulerPhi[#]]&] (* Harvey P. Dale, Dec 11 2010 *)
Join[{1}, Sort @ Flatten @ Table[2^i*3^j, {i, 2, Log2[m], 2}, {j, 0, Log[3, m/2^i], 2}]] (* Amiram Eldar, Oct 29 2020 *)

j=[]; for(n=1,2000, if(Mod(n^2,eulerphi(n^2))==0,j=concat(j,n^2))); j

{ n=0; for (m=1, 10^9, s=m^2; if (s%eulerphi(s)==0, write("b063755.txt", n++, " ", s); if (n==160, break)) ) } \\ Harry J. Smith, Aug 29 2009

From Amiram Eldar, Oct 29 2020: (Start)
a(n) = A007694(n)^2.
Sum_{n>=1} 1/a(n) = 11/8. (End)

More terms from Dean Hickerson, Aug 15 2001

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

A055458 a(n) = smallest composite solution x to the equation phi(x+2n) = phi(x)+2n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A086411 Greatest prime factor of 3-smooth numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A062356 a(n) = floor(n/phi(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A063872 Let m be the n-th positive integer such that phi(m) is divisible by m - phi(m). Then a(n) = phi(m)/(m - phi(m)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A054740 Cototient(n)/totient(n) when this is an integer.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

A063755 Squares k which are divisible by phi(k).

Views

Author

Keywords