A333386 Number of solutions to x^y == 0 (mod n) where 0 <= x < n and 1 <= y <= n.

1, 2, 3, 7, 5, 6, 7, 27, 25, 10, 11, 23, 13, 14, 15, 113, 17, 52, 19, 39, 21, 22, 23, 91, 121, 26, 229, 55, 29, 30, 31, 469, 33, 34, 35, 211, 37, 38, 39, 155, 41, 42, 43, 87, 133, 46, 47, 369, 337, 246, 51, 103, 53, 472, 55, 219, 57, 58, 59, 119, 61, 62, 187, 1945

Offset

1,2

Links

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

Formula

For prime p: a(p) = p, the solutions are 0^y for y = 1..p and a(p^k) = p^(2*k-1) + p^(k-1) - 1 - (p-1)*Sum_{j=0..k-2} p^j*ceiling(k/(k-j-1)).

a(n)>=n, with equality if and only if n is squarefree. - Robert Israel, Oct 08 2020

Example

a(4) = 7, because there are 7 solutions to x^y == 0 (mod 4): 0^1 == 0, 0^2 == 0, 0^3 == 0, 0^4 == 0, 2^2 == 0, 2^3 == 0, 2^4 == 0.

Maple

f:= proc(n) local F, q, T, x, ymin;
     F:= ifactors(n)[2];
     T:= n;
     q:= mul(t[1], t=F);
     for x from q to n-1 by q do
       ymin:= ceil(max(seq(t[2]/padic:-ordp(x, t[1]), t=F)));
       T:= T + n-ymin+1;
     od;
     T
end proc:
map(f, [$1..100]); # Robert Israel, Oct 08 2020

Mathematica

a[n_] := Sum[If[PowerMod[x, y, n] == 0, 1, 0], {x, 0, n-1}, {y, 1, n}];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 06 2023 *)

Prog

(PARI) a(n) = sum(x=0, n-1, sum (y=1, n, Mod(x, n)^y == 0)); \\ Michel Marcus, Mar 20 2020

Crossrefs

Cf. A333387, A333388.

Sequence in context: A330423 A235801 A076986 * A357579 A334126 A341717

Adjacent sequences: A333383 A333384 A333385 * A333387 A333388 A333389

Keyword

nonn

Author

Franz Vrabec, Mar 18 2020

Extensions

More terms from Jinyuan Wang, Mar 20 2020

Status

approved