login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Robert Israel, Table of n, a(n) for n = 1..10000

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

Cf. A333386, A333388.

Sequence in context: A330394 A084407 A114526 * A178126 A162202 A210380

Adjacent sequences:  A333384 A333385 A333386 * A333388 A333389 A333390

KEYWORD

nonn

AUTHOR

Franz Vrabec, Mar 18 2020

EXTENSIONS

More terms from Hugo Pfoertner, Mar 22 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 09:09 EDT 2021. Contains 345126 sequences. (Running on oeis4.)