A385318 Number of nonnegative s < n such that s^s == (-s)^s (mod n).

1, 2, 2, 2, 3, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 8, 9, 12, 10, 10, 11, 12, 12, 12, 15, 14, 18, 14, 15, 16, 16, 16, 17, 18, 18, 18, 19, 20, 20, 20, 21, 22, 22, 22, 24, 24, 24, 24, 28, 30, 26, 26, 27, 36, 28, 28, 29, 30, 30, 30, 31, 32, 33, 32, 33, 34, 34, 34, 35

Offset: 1

Author

Juri-Stepan Gerasimov, Jul 31 2025

Keywords

• nonn
• changed

Comments

From Robert Israel, Aug 01 2025: (Start)

a(n) = ceiling(n/2) + the number of odd s < n such that 2 * s^s == 0 (mod n).

If n is divisible by 4, there are no such s, so a(n) = n/2.

If n == 2 (mod 4), then s = n/2 works, so a(n) >= n/2 + 1. (End)

Crossrefs

Cf. A065295, A384781, A385103, A386409.

Programs

Magma

[#[s: s in [0..n-1] | Modexp(s,s,n) eq Modexp(-s,s,n)]: n in [1..100]];

Maple

f:= proc(n) local s;
  ceil(n/2) + nops(select(s -> 2 * s &^ s mod n = 0, [seq(s, s = 1 .. n-1, 2)]))
end proc:
map(f, [$1..100]); # Robert Israel, Aug 01 2025

Mathematica

a[n_] := Count[Range[0, n-1], ?(PowerMod[#, #, n] == PowerMod[-#, #, n] &)]; Array[a, 100] (* _Amiram Eldar, Jul 31 2025 *)

PARI

a(n) = sum(s=0, n-1, Mod(s, n)^s == Mod(-s, n)^s); \\ Michel Marcus, Aug 07 2025