A333386 - OEIS

%I #24 Feb 06 2023 07:13:03

%S 1,2,3,7,5,6,7,27,25,10,11,23,13,14,15,113,17,52,19,39,21,22,23,91,

%T 121,26,229,55,29,30,31,469,33,34,35,211,37,38,39,155,41,42,43,87,133,

%U 46,47,369,337,246,51,103,53,472,55,219,57,58,59,119,61,62,187,1945

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

%H Robert Israel, <a href="/A333386/b333386.txt">Table of n, a(n) for n = 1..10000</a>

%F 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)).

%F a(n)>=n, with equality if and only if n is squarefree. - _Robert Israel_, Oct 08 2020

%e 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.

%p f:= proc(n) local F,q,T,x,ymin;

%p      F:= ifactors(n)[2];

%p      T:= n;

%p      q:= mul(t[1],t=F);

%p      for x from q to n-1 by q do

%p        ymin:= ceil(max(seq(t[2]/padic:-ordp(x,t[1]), t=F)));

%p        T:= T + n-ymin+1;

%p      od;

%p      T

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Oct 08 2020

%t a[n_] := Sum[If[PowerMod[x, y, n] == 0, 1, 0], {x, 0, n-1}, {y, 1, n}];

%t Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Feb 06 2023 *)

%o (PARI) a(n) = sum(x=0, n-1, sum (y=1, n, Mod(x, n)^y == 0)); \\ _Michel Marcus_, Mar 20 2020

%Y Cf. A333387, A333388.

%K nonn

%O 1,2

%A _Franz Vrabec_, Mar 18 2020

%E More terms from _Jinyuan Wang_, Mar 20 2020