|
%I #22 Jun 09 2020 15:45:16
%S 1,2,4,6,9,9,16,20,21,19,28,30,41,33,48,56,49,45,64,70,83,57,64,108,
%T 85,83,90,112,105,103,136,144,141,99,186,150,169,129,218,260,181,175,
%U 196,190,251,129,136,312,217,175,270,296,201,189,324,414,323,211,172
%N Number of solutions to x^y == 1 (mod n) where 0 <= x < n and 1 <= y <= n.
%H Robert Israel, <a href="/A333387/b333387.txt">Table of n, a(n) for n = 1..10000</a>
%F 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.
%F a(2^k) = (2*k-1)*2^(k-1) for k >= 1.
%e 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).
%p f:= proc(n) local t,x,r;
%p t:= 0;
%p for x from 1 to n-1 do if igcd(n,x) = 1 then
%p r:= numtheory:-order(x,n);
%p t:= t + floor(n/r)
%p fi od;
%p t
%p end proc:
%p f(1):= 1:
%p map(f, [$1..100]): # _Robert Israel_, Mar 25 2020
%t a[n_] := If[n == 1, 1, Sum[Boole[PowerMod[x, y, n] == 1], {x, 0, n - 1}, {y, 1, n}]];
%t Array[a, 100] (* _Jean-François Alcover_, Jun 08 2020 *)
%o (PARI) a(n) = sum(x=0, n-1, sum (y=1, n, Mod(x, n)^y == 1)); \\ _Michel Marcus_, Mar 20 2020
%Y Cf. A333386, A333388.
%K nonn
%O 1,2
%A _Franz Vrabec_, Mar 18 2020
%E More terms from _Hugo Pfoertner_, Mar 22 2020
|
