login
A333387
Number of solutions to x^y == 1 (mod n) where 0 <= x < n and 1 <= y <= n.
4
1, 2, 4, 6, 9, 9, 16, 20, 21, 19, 28, 30, 41, 33, 48, 56, 49, 45, 64, 70, 83, 57, 64, 108, 85, 83, 90, 112, 105, 103, 136, 144, 141, 99, 186, 150, 169, 129, 218, 260, 181, 175, 196, 190, 251, 129, 136, 312, 217, 175, 270, 296, 201, 189, 324, 414, 323, 211, 172
OFFSET
1,2
LINKS
FORMULA
If n possesses a primitive root (i.e., n is in A033948), then a(n) = Sum_{j=1..n} gcd(j,phi(n)); phi(n)=A000010(n), the Euler totient function.
a(2^k) = (2*k-1)*2^(k-1) for k >= 1.
EXAMPLE
a(3) = 4 because there are 4 solutions to x^y == 1 (mod 3): 1^1 == 1 (3), 1^2 == 1 (3), 1^3 == 1 (3), 2^2 == 1 (3).
MAPLE
f:= proc(n) local t, x, r;
t:= 0;
for x from 1 to n-1 do if igcd(n, x) = 1 then
r:= numtheory:-order(x, n);
t:= t + floor(n/r)
fi od;
t
end proc:
f(1):= 1:
map(f, [$1..100]): # Robert Israel, Mar 25 2020
MATHEMATICA
a[n_] := If[n == 1, 1, Sum[Boole[PowerMod[x, y, n] == 1], {x, 0, n - 1}, {y, 1, n}]];
Array[a, 100] (* Jean-François Alcover, Jun 08 2020 *)
PROG
(PARI) a(n) = sum(x=0, n-1, sum (y=1, n, Mod(x, n)^y == 1)); \\ Michel Marcus, Mar 20 2020
CROSSREFS
Sequence in context: A330394 A084407 A114526 * A178126 A359515 A162202
KEYWORD
nonn
AUTHOR
Franz Vrabec, Mar 18 2020
EXTENSIONS
More terms from Hugo Pfoertner, Mar 22 2020
STATUS
approved