|
|
A127473
|
|
a(n) = phi(n)^2.
|
|
23
|
|
|
1, 1, 4, 4, 16, 4, 36, 16, 36, 16, 100, 16, 144, 36, 64, 64, 256, 36, 324, 64, 144, 100, 484, 64, 400, 144, 324, 144, 784, 64, 900, 256, 400, 256, 576, 144, 1296, 324, 576, 256, 1600, 144, 1764, 400, 576, 484, 2116, 256, 1764, 400, 1024, 576, 2704, 324, 1600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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
a(n) is the number of solutions to gcd(xy, n) = 1 with x, y in [0, n-1].
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)
|
|
LINKS
|
|
|
FORMULA
|
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
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
|
|
EXAMPLE
|
a(5) = 16 since phi(5) = 4.
|
|
MAPLE
|
A127473 := proc(n) numtheory[phi](n)^2 ; end proc:
|
|
MATHEMATICA
|
|
|
PROG
|
|
|
CROSSREFS
|
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).
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|