

A002618


a(n) = n*phi(n).
(Formerly M1568 N0611)


111



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



OFFSET

1,2


COMMENTS

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)mydeja.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. AdamsWatters, 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.)
Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts.  ZhiWei Sun, Sep 24 2015
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 oddindexed 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)


REFERENCES

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


LINKS



FORMULA

Multiplicative with a(p^e) = (p1)*p^(2e1).  David W. Wilson, Aug 01 2001
Dirichlet g.f.: zeta(s2)/zeta(s1).  R. J. Mathar, Feb 09 2011
G.f.: x + 2*Sum_{k>=1} mu(k)*k*x^k/(1  x^k)^3.  Ilya Gutkovskiy, Jan 03 2017
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


EXAMPLE

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


MAPLE

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


MATHEMATICA



PROG

(Sage) [euler_phi(n^2) for n in range(1, 51)] # Zerinvary Lajos, Jun 06 2009
(Haskell)
(Python)
from sympy import totient as phi
def a(n): return n*phi(n)


CROSSREFS

Cf. A002619, A047918, A000010, A053650, A053191, A053192, A036689, A058161, A009262, A082473 (same terms, sorted into ascending order), A256545, A327172 (a left inverse), A327173, A065484.


KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



