|
%I M1568 N0611 #199 Jan 30 2024 11:04:48
%S 1,2,6,8,20,12,42,32,54,40,110,48,156,84,120,128,272,108,342,160,252,
%T 220,506,192,500,312,486,336,812,240,930,512,660,544,840,432,1332,684,
%U 936,640,1640,504,1806,880,1080,1012,2162,768,2058,1000
%N a(n) = n*phi(n).
%C Also Euler phi function of n^2.
%C 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
%C Order of metacyclic group of polynomial of degree n. - _Artur Jasinski_, Jan 22 2008
%C 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
%C 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
%C 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
%C 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.)
%C a(p) = p*(p-1) a pronic number, see A036689 and A002378. - _Fred Daniel Kline_, Mar 30 2015
%C 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
%C From _Jianing Song_, Aug 25 2023: (Start)
%C 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.
%C 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)
%D Peter Giblin, Primes and Programming: An Introduction to Number Theory with Computing. Cambridge: Cambridge University Press (1993) p. 116, Exercise 1.10.
%D J. L. Lagrange, Oeuvres, Vol. III Paris 1869.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Michael De Vlieger, <a href="/A002618/b002618.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H Daniel Fischer, answer to <a href="https://math.stackexchange.com/questions/539558/injectivity-of-the-function-n-times-the-euler-totient-of-n">Injectivity of the function n times the Euler Totient of n</a>, Mathematics Stack Exchange, October 2013.
%H Mikhail R. Gabdullin and Vitalii V. Iudelevich, <a href="https://arxiv.org/abs/2201.09287">Numbers of the form kf(k)</a>, arXiv:2201.09287 [math.NT] (2022).
%H Dmitry Krachun and Zhi-Wei Sun, <a href="https://arxiv.org/abs/2001.03736">Each positive rational number has the form phi(m^2)/phi(n^2)</a>, arXiv:2001.03736 [math.HO], 2020. See also <a href="https://doi.org/10.1080/00029890.2020.1801294">The American Mathematical Monthly</a> (2020) Vol. 127, Issue 9, 847-849.
%H F. Luca and A. O. Munagi, <a href="https://doi.org/10.2478/aicu-2014-0053">The number of permutations which form arithmetic progressions modulo m</a>, Annals of the Alexandru Ioan Cuza University, 2014, DOI: 10.2478/aicu-2014-0053. [Broken link]
%H C. L. Mallows and N. J. A. Sloane, <a href="/A002618/a002618_1.pdf">Notes on A002618, A002619, etc.</a>
%H W. Peremans, <a href="https://doi.org/10.1016/S1385-7258(57)50078-4">Completeness of Holomorphs</a>, Nederl. Akad. Wetensch. Indag. Math. Proc. Ser. A, 60. (1957) 608-619.
%H N. J. A. Sloane, <a href="/A002618/a002618_2.pdf">Notes on A002618, A002619, etc.</a>
%H J. E. A. Steggall, <a href="http://www.handweaving.net/DAItemDetail.aspx?ItemID=3237">On the numbers of patterns which can be derived from certain elements</a>, Mess. Math., 37 (1907), 56-61.
%H J. E. A. Steggall, <a href="/A002618/a002618.pdf">On the numbers of patterns which can be derived from certain elements</a>, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Holomorph_(mathematics)">Holomorph</a>.
%H Wordpress, <a href="https://ysharifi.wordpress.com/2022/09/14/automorphisms-of-dihedral-groups">Automorphisms of dihedral groups</a>.
%F Multiplicative with a(p^e) = (p-1)*p^(2e-1). - _David W. Wilson_, Aug 01 2001
%F Dirichlet g.f.: zeta(s-2)/zeta(s-1). - _R. J. Mathar_, Feb 09 2011
%F a(n) = A173557(n) * A102631(n). - _R. J. Mathar_, Mar 30 2011
%F From _Wolfdieter Lang_, May 12 2011: (Start)
%F a(n)/2 = A023896(n), n >= 2.
%F a(n)/2 = (1/n) * Sum_{k=1..n-1, gcd(k,n)=1} k, n >= 2 (see A023896 and A076512/A109395). (End)
%F a(n) = lcm(phi(n^2),n). - _Enrique Pérez Herrero_, May 11 2012
%F a(n) = phi(n^2). - _Wesley Ivan Hurt_, Jun 16 2013
%F a(n) = A009195(n) * A009262(n). - _Michel Marcus_, Oct 24 2013
%F G.f.: -x + 2*Sum_{k>=1} mu(k)*k*x^k/(1 - x^k)^3. - _Ilya Gutkovskiy_, Jan 03 2017
%F a(n) = A082473(A327173(n)), A327172(a(n)) = n. -- _Antti Karttunen_, Sep 29 2019
%F Sum_{n>=1} 1/a(n) = 2.203856... (A065484). - _Amiram Eldar_, Sep 30 2019
%F 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
%F 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
%e a(4) = 8 since phi(4) = 2 and 4 * 2 = 8.
%e a(5) = 20 since phi(5) = 4 and 5 * 4 = 20.
%p with(numtheory):a:=n->phi(n^2): seq(a(n), n=1..50); # _Zerinvary Lajos_, Oct 07 2007
%t Table[n EulerPhi[n], {n, 100}] (* _Artur Jasinski_, Jan 22 2008 *)
%o (MuPAD) numlib::phi(n^2)$ n=1..81 // _Zerinvary Lajos_, May 13 2008
%o (Sage) [euler_phi(n^2) for n in range(1,51)] # _Zerinvary Lajos_, Jun 06 2009
%o (Magma) [n*EulerPhi(n): n in [1..150]]; // _Vincenzo Librandi_, Apr 04 2011
%o (PARI) a(n)=n*eulerphi(n) \\ _Charles R Greathouse IV_, Nov 20 2012
%o (Haskell)
%o a002618 n = a000010 n * n -- _Reinhard Zumkeller_, Dec 21 2012
%o (Python)
%o from sympy import totient as phi
%o def a(n): return n*phi(n)
%o print([a(n) for n in range(1, 51)]) # _Michael S. Branicky_, Mar 16 2022
%Y First column of A047916.
%Y Cf. A002619, A047918, A000010, A053650, A053191, A053192, A036689, A058161, A009262, A082473 (same terms, sorted into ascending order), A256545, A327172 (a left inverse), A327173, A065484.
%Y Subsequence of A323333.
%K nonn,easy,nice,mult,look
%O 1,2
%A _N. J. A. Sloane_
%E Better description from _Labos Elemer_, Feb 18 2000
| 