A053650 -id:A053650 - cp's OEIS frontend

A002618 a(n) = n*phi(n).

1, 2, 6, 8, 20, 12, 42, 32, 54, 40, 110, 48, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500, 312, 486, 336, 812, 240, 930, 512, 660, 544, 840, 432, 1332, 684, 936, 640, 1640, 504, 1806, 880, 1080, 1012, 2162, 768, 2058, 1000

Offset: 1

N. J. A. Sloane

Also Euler phi function of n^2.
For n >= 3, a(n) is also the size of the automorphism group of the dihedral group of order 2n. This automorphism group is isomorphic to the group of transformations x -> ax + b, where a, b and x are integers modulo n and a is coprime to n. Its order is n*phi(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 18 2001
Order of metacyclic group of polynomial of degree n. - Artur Jasinski, Jan 22 2008
It appears that this sequence gives the number of permutations of 1, 2, 3, ..., n that are arithmetic progressions modulo n. - John W. Layman, Aug 27 2008
The conjecture by Layman is correct. Obviously any such permutation must have an increment that is prime to n, and almost as obvious that any such increment will work, with any starting value; hence phi(n) * n total. - Franklin T. Adams-Watters, Jun 09 2009
Consider the numbers from 1 to n^2 written line by line as an n X n square: a(n) = number of numbers that are coprime to all their horizontal and vertical immediate neighbors. - Reinhard Zumkeller, Apr 12 2011
n -> a(n) is injective: a(m) = a(n) implies m = n. - Franz Vrabec, Dec 12 2012 (See Mathematics Stack Exchange link for a proof.)
a(p) = p*(p-1) a pronic number, see A036689 and A002378. - Fred Daniel Kline, Mar 30 2015
Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015
From Jianing Song, Aug 25 2023: (Start)
a(n) is the order of the holomorph (see the Wikipedia link) of the cyclic group of order n. Note that Hol(C_n) and Aut(D_{2n}) are isomorphic unless n = 2, where D_{2n} is the dihedral group of order 2*n. See the Wordpress link.
The odd-indexed terms form a subsequence of A341298: the holomorph of an abelian group of odd order is a complete group. See Theorem 3.2, Page 618 of the W. Peremans link. (End)

			a(4) = 8 since phi(4) = 2 and 4 * 2 = 8.
a(5) = 20 since phi(5) = 4 and 5 * 4 = 20.

Peter Giblin, Primes and Programming: An Introduction to Number Theory with Computing. Cambridge: Cambridge University Press (1993) p. 116, Exercise 1.10.
J. L. Lagrange, Oeuvres, Vol. III Paris 1869.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Daniel Fischer, answer to Injectivity of the function n times the Euler Totient of n, Mathematics Stack Exchange, October 2013.
Mikhail R. Gabdullin and Vitalii V. Iudelevich, Numbers of the form kf(k), arXiv:2201.09287 [math.NT] (2022).
Dmitry Krachun and Zhi-Wei Sun, Each positive rational number has the form phi(m^2)/phi(n^2), arXiv:2001.03736 [math.HO], 2020. See also The American Mathematical Monthly (2020) Vol. 127, Issue 9, 847-849.
F. Luca and A. O. Munagi, The number of permutations which form arithmetic progressions modulo m, Annals of the Alexandru Ioan Cuza University, 2014, DOI: 10.2478/aicu-2014-0053. [Broken link]
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
W. Peremans, Completeness of Holomorphs, Nederl. Akad. Wetensch. Indag. Math. Proc. Ser. A, 60. (1957) 608-619.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]
Wikipedia, Holomorph.
Wordpress, Automorphisms of dihedral groups.

First column of A047916.
Cf. A002619, A011755 (partial sums), A047918, A000010, A053650, A053191, A053192, A036689, A058161, A009262, A082473 (same terms, sorted into ascending order), A256545, A327172 (a left inverse), A327173, A065484.
Subsequence of A323333.

a002618 n = a000010 n * n  -- Reinhard Zumkeller, Dec 21 2012

[n*EulerPhi(n): n in [1..150]]; // Vincenzo Librandi, Apr 04 2011

with(numtheory):a:=n->phi(n^2): seq(a(n), n=1..50); # Zerinvary Lajos, Oct 07 2007

Table[n EulerPhi[n], {n, 100}] (* Artur Jasinski, Jan 22 2008 *)

numlib::phi(n^2)$ n=1..81 // Zerinvary Lajos, May 13 2008

a(n)=n*eulerphi(n) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import totient as phi
def a(n): return n*phi(n)
print([a(n) for n in range(1, 51)]) # Michael S. Branicky, Mar 16 2022

[euler_phi(n^2) for n in range(1,51)] # Zerinvary Lajos, Jun 06 2009

Multiplicative with a(p^e) = (p-1)*p^(2e-1). - David W. Wilson, Aug 01 2001
Dirichlet g.f.: zeta(s-2)/zeta(s-1). - R. J. Mathar, Feb 09 2011
a(n) = A173557(n) * A102631(n). - R. J. Mathar, Mar 30 2011
From Wolfdieter Lang, May 12 2011: (Start)
a(n)/2 = A023896(n), n >= 2.
a(n)/2 = (1/n) * Sum_{k=1..n-1, gcd(k,n)=1} k, n >= 2 (see A023896 and A076512/A109395). (End)
a(n) = lcm(phi(n^2),n). - Enrique Pérez Herrero, May 11 2012
a(n) = phi(n^2). - Wesley Ivan Hurt, Jun 16 2013
a(n) = A009195(n) * A009262(n). - Michel Marcus, Oct 24 2013
G.f.: -x + 2*Sum_{k>=1} mu(k)*k*x^k/(1 - x^k)^3. - Ilya Gutkovskiy, Jan 03 2017
a(n) = A082473(A327173(n)), A327172(a(n)) = n. -- Antti Karttunen, Sep 29 2019
Sum_{n>=1} 1/a(n) = 2.203856... (A065484). - Amiram Eldar, Sep 30 2019
Define f(x) = #{n <= x: a(n) <= x}. Gabdullin & Iudelevich show that f(x) ~ c*sqrt(x) for c = Product_{p prime} (1 + 1/(p*(p - 1 + sqrt(p^2 - p)))) = 1.3651304521525857... - Charles R Greathouse IV, Mar 16 2022
a(n) = Sum_{d divides n} A001157(d)*A046692(n/d); that is, the Dirichlet convolution of sigma_2(n) and the Dirichlet inverse of sigma_1(n). - Peter Bala, Jan 26 2024

Better description from Labos Elemer, Feb 18 2000

A036689 Product of a prime and the previous number.

Original entry on oeis.org

2, 6, 20, 42, 110, 156, 272, 342, 506, 812, 930, 1332, 1640, 1806, 2162, 2756, 3422, 3660, 4422, 4970, 5256, 6162, 6806, 7832, 9312, 10100, 10506, 11342, 11772, 12656, 16002, 17030, 18632, 19182, 22052, 22650, 24492, 26406, 27722, 29756, 31862, 32580, 36290, 37056, 38612, 39402, 44310

Offset: 1

Felice Russo

Records in A002618. - Artur Jasinski, Jan 23 2008

Also records in A174857. - Vladimir Shevelev, Mar 31 2010

			2*1, 3*2, 5*4, 7*6, 11*10, 13*12, 17*16, ...

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index to sequences related to prime powers

Cf. A000040, A001248, A002618, A005596, A053650, A053192, A053193, A053650, A082695, A117495, A136141.
Twice the terms of A008837.
Subsequence of A002378 (oblong numbers).
Column 1 of A257251. (Row 1 of A257252.)
Column 2 of A379010.

a036689 n = a036689_list !! (n-1)
a036689_list = zipWith (*) a000040_list $ map pred a000040_list
-- Reinhard Zumkeller, Sep 17 2011

[ n*(n-1): n in PrimesUpTo(220) ]; // Bruno Berselli, Apr 11 2011

A036689 := proc(n) local p ; p := ithprime(n) ; p*(p-1) ; end proc: # R. J. Mathar, Apr 11 2011

Table[Prime[n] EulerPhi[Prime[n]], {n, 100}] (* Artur Jasinski, Jan 23 2008 *)
Table[Prime[n] (Prime[n] - 1), {n, 1, 50}] (* Bruno Berselli, Apr 22 2014 *)
#(#-1)&/@Prime[Range[50]] (* Harvey P. Dale, Sep 08 2019 *)

forprime(p=2,1e3,print1(p^2-p", ")) \\ Charles R Greathouse IV, Jun 10 2011

A036689(n) = ((p->(p-1)*p)(prime(n))); \\ Antti Karttunen, Dec 14 2024

(define (A036689 n) (* (A000040 n) (- (A000040 n) 1))) ;; Antti Karttunen, May 01 2015

a(n) = prime(n) * (prime(n) - 1).
a(n) = phi(prime(n)^2) = A000010(A001248(n)).
a(n) = prime(n) * phi(prime(n)). - Artur Jasinski, Jan 23 2008
From Reinhard Zumkeller, Sep 17 2011: (Start)
a(n) = A000040(n) * A006093(n) = A001248(n) - A000040(n).
A006530(a(n)) = A000040(n). (End)
a(n) = A009262(prime(n)). - Enrique Pérez Herrero, May 12 2012
a(n) = prime(n)! mod (prime(n)^2). - J. M. Bergot, Apr 10 2014
a(n) = 2*A008837(n). - Antti Karttunen, May 01 2015
Sum_{n>=1} 1/a(n) = A136141. - Amiram Eldar, Nov 09 2020
From Amiram Eldar, Jan 23 2021: (Start)
Product_{n>=1} (1 + 1/a(n)) = zeta(2)*zeta(3)/zeta(6) (A082695).
Product_{n>=1} (1 - 1/a(n)) = A005596. (End)

Deleted two incorrect comments. - N. J. A. Sloane, May 07 2020

A053191 a(n) = n^2 * phi(n).

Original entry on oeis.org

1, 4, 18, 32, 100, 72, 294, 256, 486, 400, 1210, 576, 2028, 1176, 1800, 2048, 4624, 1944, 6498, 3200, 5292, 4840, 11638, 4608, 12500, 8112, 13122, 9408, 23548, 7200, 28830, 16384, 21780, 18496, 29400, 15552, 49284, 25992, 36504, 25600, 67240

Offset: 1

Labos Elemer, Mar 02 2000

Number of invertible 2 X 2 symmetric matrices over Z(n). - T. D. Noe, Jan 13 2006
Note that A115077 gives the number of 2 X 2 symmetric matrices having nonzero determinant. However, for composite n, a nonzero determinant is not sufficient for the matrix to be invertible; the determinant must also be relatively prime to n. - T. D. Noe, Jan 13 2006
Also Euler phi function of n^3.
For n^k, EulerPhi(n^k) = n^(k-1)*EulerPhi(n). The same holds if Phi is replaced by the cototient function.
Also, the sum of the degrees of the irreducible representations of the group GL(2,Z_n) (sequence A000252). - Sharon Sela (sharonsela(AT)hotmail.com), Feb 06 2002

			n=5: n^3 = 125, EulerPhi(125) = 125 - 25 = 100.

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000252 (number of invertible 2 X 2 matrices over Z(n)), A115075, A115076, A115077.

Cf. A000010, A051953, A002618, A053650, A053192, A001248, A319087.

[ n^2*EulerPhi(n) : n in [1..100] ]; // Vincenzo Librandi, Apr 21 2011

with(numtheory):a:=n->phi(n^3): seq(a(n), n=1..41); # Zerinvary Lajos, Oct 07 2007

Table[cnt=0; Do[m={{a, b}, {b, c}}; If[Det[m, Modulus->n]>0 && MatrixQ[Inverse[m, Modulus->n]], cnt++ ], {a, 0, n-1}, {b, 0, n-1}, {c, 0, n-1}]; cnt, {n, 2, 50}] (* T. D. Noe, Jan 13 2006 *)
Table[n^2*EulerPhi[n],{n,1,40}] (* Vladimir Joseph Stephan Orlovsky, Nov 10 2009 *)

a(n) = n^2*eulerphi(n); \\ Michel Marcus, Oct 31 2017

[n^2*euler_phi(n) for n in range(1, 42)] # Zerinvary Lajos, Jun 06 2009

a(n) = n^2 * phi(n) = A000010(n^3).
Dirichlet g.f.: zeta(s-3)/zeta(s-2). - R. J. Mathar, Feb 09 2011
The n-th term of the Dirichlet inverse is n^2 * A023900(n) = (-1)^omega(n) * a(n) / A003557(n), where omega = A001221. - Álvar Ibeas, Nov 24 2017
Sum_{n>=1} 1/a(n) = Product_{p prime} (1 + p/(p^4 - p^3 - p + 1)) = 1.38097852211302096879... - Amiram Eldar, Dec 06 2020

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 05 2007

A058764 Smallest number x such that cototient(x) = 2^n.

Original entry on oeis.org

2, 4, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472

Offset: 0

Labos Elemer, Jan 02 2001

Since the cototient of 3*2^n is 2^(n+1), upper bounds are given by A007283(n-1). - R. J. Mathar, Oct 13 2008

A058764(n+1) is the number of different walks with n steps in the graph G = ({1,2,3,4}, {{1,2}, {2,3}, {3,4}}). - Aldo González Lorenzo, Feb 27 2012

			a(5) = 48, cototient(48) = 48-Phi(48) = 48-16 = 32. For n>2, a(n) = 3*2^(n-1); largest solutions = 2^(n+1). Prime factors of solutions: 2 and Mersenne-primes were found only.

Jud McCranie, Table of n, a(n) for n = 0..46

Cf. A051953, A053579, A053650.
Cf. A042950. - R. J. Mathar, Jan 30 2009
Cf. A007283.

Function[s, Flatten@ Map[First@ Position[s, #] &, 2^Range[0, Floor@ Log2@ Max@ s]]]@ Table[n - EulerPhi@ n, {n, 10^7}] (* Michael De Vlieger, Dec 17 2016 *)

a(n) = {x = 1; while(x - eulerphi(x) != 2^n, x++); x;} \\ Michel Marcus, Dec 11 2013

a(n) = if(n>1,3,4)<<(n-1) \\ M. F. Hasler, Nov 10 2016

a(n) = min { x | A051953(x) = 2^n }.

a(n) = (if n>1 then 3 else 4)*2^(n-1) = A007283(n-1) for n>1. (Conjectured.) - M. F. Hasler, Nov 10 2016

Edited by M. F. Hasler, Nov 10 2016

a(27)-a(31) from Jud McCranie, Jul 13 2017

A053192 a(n) is the cototient of n^3.

Original entry on oeis.org

0, 4, 9, 32, 25, 144, 49, 256, 243, 600, 121, 1152, 169, 1568, 1575, 2048, 289, 3888, 361, 4800, 3969, 5808, 529, 9216, 3125, 9464, 6561, 12544, 841, 19800, 961, 16384, 14157, 20808, 13475, 31104, 1369, 28880, 22815, 38400, 1681, 52920, 1849, 46464

Offset: 1

Labos Elemer, Mar 02 2000

For n^k, n^k - EulerPhi(n^k) = n^(k-1)*(n-EulerPhi(n)), or cototient(n^k) = n^(k-1)*cototient(n). A similar relation holds for Euler totient function.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A000010, A051953, A002618, A053650, A053191, A001248, A229099.

[n^3-EulerPhi(n^3): n in [1..44]]; // Vincenzo Librandi, Jul 28 2013

Table[(n^3 - EulerPhi[n^3]), {n, 1, 50}] (* Vincenzo Librandi, Jul 27 2013 *)

a(n) = n^3 - eulerphi(n^3) \\ Michel Marcus, Jul 26 2013

a(n) = n^2*Cototient(n) = A051953(n^3) = n^3 - EulerPhi(n^3) = Cototient(n^3).
a(prime(n)) = A051953(prime(n)^3) = A001248(n).
Sum_{k=1..n} a(k) ~ c * n^4 / 4, where c = 1 - 6/Pi^2 (A229099). - Amiram Eldar, Dec 15 2023

A053198 Totients of consecutive pure powers of primes.

Original entry on oeis.org

2, 4, 6, 8, 20, 18, 16, 42, 32, 54, 110, 100, 64, 156, 162, 128, 272, 294, 342, 256, 506, 500, 486, 812, 930, 512, 1210, 1332, 1640, 1806, 1024, 1458, 2028, 2162, 2058, 2756, 2500, 3422, 3660, 2048, 4422, 4624, 4970, 5256, 6162, 4374, 6498, 6806, 7832, 4096

Offset: 1

Labos Elemer, Mar 03 2000

nonn

Totients of prime powers are prime powers only for powers of 2.

			The 10th pure power of prime (but not a prime) is 81, so a(10) = EulerPhi(81) = 54.

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

Cf. A000010, A051953, A001248, A002618, A036689, A053650, A053191, A053192, A086242.

EulerPhi[Select[Range[2^13], CompositeQ[#] && PrimePowerQ[#] &]] (* Amiram Eldar, Dec 21 2020 *)

a(n) = A000010(A025475(n+1)).
Numbers of the form phi(p^k) = (p-1)*p^(k-1), where p is prime and k > 1.
Sum_{n>=1} 1/a(n) = Sum_{p prime} 1/(p-1)^2 = A086242 = 1.3750649947... - Amiram Eldar, Dec 21 2020

A053211 Cototients of consecutive pure powers of primes.

Original entry on oeis.org

2, 4, 3, 8, 5, 9, 16, 7, 32, 27, 11, 25, 64, 13, 81, 128, 17, 49, 19, 256, 23, 125, 243, 29, 31, 512, 121, 37, 41, 43, 1024, 729, 169, 47, 343, 53, 625, 59, 61, 2048, 67, 289, 71, 73, 79, 2187, 361, 83, 89, 4096, 97, 101, 103, 107, 109, 529, 113, 1331, 3125, 127

Offset: 1

Labos Elemer, Mar 03 2000

nonn

Cototients of prime powers do not remain always prime powers, but are primes if their exponent is 2.

			The 10th pure power of prime (but not a prime) is 81, so a(10) = 81 - EulerPhi(81) = 81 - 54 = 27. For n=p^2, a(n)=p.

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Log log scatterplot of a(n) n = 1..2^20, showing even a(n) in blue, 3 | a(n) in green, and prime a(n) in red, else black.

Cf. A000010, A051953, A001248, A002618, A036689, A053650, A053191, A053192, A246547.

Map[# - EulerPhi@ # &, Select[Range[16200], And[! PrimeQ@ #, PrimePowerQ@ #] &]] (* Michael De Vlieger, Jun 11 2018 *)
With[{nn = 2^14}, Map[Times @@ Map[#1^(#2 - 1) & @@ FactorInteger[#][[1]]] &, Select[Union@ Flatten@ Table[a^2*b^3, {b, nn^(1/3)}, {a, Sqrt[nn/b^3]}], PrimePowerQ] ] ] (* Michael De Vlieger, Mar 11 2023 *)

a(n) = A051953(A025475(n+1)) = cototient(p^k) = p^(k-1).

A307705 Expansion of Product_{k>=1} 1/(1 - x^k)^(k-phi(k)), where phi() is the Euler totient function (A000010).

Original entry on oeis.org

1, 0, 1, 1, 3, 2, 8, 5, 16, 15, 34, 30, 75, 66, 144, 150, 285, 292, 566, 585, 1062, 1170, 1988, 2205, 3729, 4159, 6755, 7785, 12214, 14147, 21957, 25560, 38709, 45839, 67884, 80747, 118332, 141244, 203614, 245330, 348396, 420971, 592439, 717659, 998248, 1215439, 1672544, 2040210, 2786687

Offset: 0

Ilya Gutkovskiy, Apr 22 2019

nonn

Euler transform of A051953.

Cf. A000010, A001157, A051953, A053650, A057660, A061255, A065764, A065827.

nmax = 48; CoefficientList[Series[Product[1/(1 - x^k)^(k - EulerPhi[k]), {k, 1, nmax}], {x, 0, nmax}], x]
nmax = 48; CoefficientList[Series[Exp[Sum[(DivisorSigma[2, k] - DivisorSigma[2, k^2]/DivisorSigma[1, k^2]) x^k/k, {k, 1, nmax}]], {x, 0, nmax}], x]
a[n_] := a[n] = If[n == 0, 1, Sum[Sum[d^2 - EulerPhi[d^2], {d, Divisors[k]}] a[n - k], {k, 1, n}]/n]; Table[a[n], {n, 0, 48}]

G.f.: exp(Sum_{k>=1} (sigma_2(k) - sigma_2(k^2)/sigma_1(k^2)) * x^k/k).
G.f.: exp(Sum_{k>=1} ( Sum_{d|k} cototient(d^2) ) * x^k/k).
a(n) ~ exp(3*((Pi^2 - 6)*Zeta(3))^(1/3) * n^(2/3) / (2*Pi)^(2/3) + 1/4) * ((Pi^2 - 6)*Zeta(3))^(1/4) / (A^3 * 2^(1/12) * 3^(1/2) * Pi^(5/6) * n^(3/4)), where A is the Glaisher-Kinkelin constant A074962. - Vaclav Kotesovec, May 06 2019

cp's OEIS Frontend

A002618 a(n) = n*phi(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Sage

Formula

Extensions

A036689 Product of a prime and the previous number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Scheme

Formula

Extensions

A053191 a(n) = n^2 * phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A058764 Smallest number x such that cototient(x) = 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A053192 a(n) is the cototient of n^3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI