login
a(n) = phi(n)^2.
24

%I #62 Mar 10 2023 12:21:07

%S 1,1,4,4,16,4,36,16,36,16,100,16,144,36,64,64,256,36,324,64,144,100,

%T 484,64,400,144,324,144,784,64,900,256,400,256,576,144,1296,324,576,

%U 256,1600,144,1764,400,576,484,2116,256,1764,400,1024,576,2704,324,1600

%N a(n) = phi(n)^2.

%C Number of maps of the form j |--> m*j + d with gcd(m, n) = 1 and gcd(d, n) = 1 from [1, 2, ..., n] to itself. - _Joerg Arndt_, Aug 29 2014

%C Right border of A127474.

%C Equals the Mobius transform (A054525) of A029939. - _Gary W. Adamson_, Aug 20 2008

%C From _Jianing Song_, Apr 14 2019: (Start)

%C a(n) is the number of solutions to gcd(xy, n) = 1 with x, y in [0, n-1].

%C Let Z_n be the ring of integers modulo n, then a(n) is the number of invertible elements in the ring Z_n[x]/(x^2 - x) (or equivalently, Z_n[x]/(x^2 + x)) with discriminant d = 1 (that is, a(n) is the size of the group G(n) = (Z_n[x]/(x^2 - x))*). Actually, G(n) is isomorphic to (Z_n)* X (Z_n)*. (End)

%H Jens Kruse Andersen, <a href="/A127473/b127473.txt">Table of n, a(n) for n = 1..10000</a>

%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence).

%F a(n) = A000010(n)^2.

%F Multiplicative with a(p^e) = (p-1)^2*p^(2e-2), e >= 1. Dirichlet g.f. zeta(s-2)*Product_{primes p} (1 - 2/p^(s-1) + 1/p^s). - _R. J. Mathar_, Apr 04 2011

%F Sum_{k>=1} 1/a(k) = A109695. - _Vaclav Kotesovec_, Sep 20 2020

%F Sum_{k>=1} (-1)^k/a(k) = (1/7) * A109695. - _Amiram Eldar_, Nov 11 2020

%F Sum_{k=1..n} a(k) ~ c * n^3, where c = (1/3) * Product_{p prime}(1 - (2*p-1)/p^3) = A065464 / 3 = 0.142749... . - _Amiram Eldar_, Oct 25 2022

%e a(5) = 16 since phi(5) = 4.

%p A127473 := proc(n) numtheory[phi](n)^2 ; end proc:

%p seq(A127473(n),n=1..40) ; # _R. J. Mathar_, Apr 04 2011

%t Table[EulerPhi[n]^2,{n,100}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 02 2012 *)

%o (Magma) [(EulerPhi(n))^2: n in [1..180]]; // _Vincenzo Librandi_, Apr 04 2011

%o (PARI) a(n) = eulerphi(n)^2; \\ _Michel Marcus_, Oct 16 2018

%Y Cf. A000010, A057434, A065464, A109695, A127474, A358714, A361148.

%Y Similar sequences: A082953 (size of (Z_n[x]/(x^2 - 1))*, d = 4), A002618 ((Z_n[x]/(x^2))*, d = 0), A079458 ((Z_n[x]/(x^2 + 1))*, d = -4), A319445 ((Z_n[x]/(x^2 - x + 1))* or (Z_n[x]/(x^2 + x + 1))*, d = -3).

%K nonn,mult

%O 1,3

%A _Gary W. Adamson_, Jan 15 2007