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,2

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)

Links

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

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 *)

Prog

(Magma) [#[s: s in [0..n-1] | Modexp(s, s, n) eq Modexp(-s, s, n)]: n in [1..100]];
(PARI) a(n) = sum(s=0, n-1, Mod(s, n)^s == Mod(-s, n)^s); \\ Michel Marcus, Aug 07 2025

Crossrefs

Cf. A065295, A384781, A385103, A386409.

Sequence in context: A369573 A117953 A128331 * A084827 A251631 A029076

Adjacent sequences: A385315 A385316 A385317 * A385319 A385320 A385321

Keyword

nonn

Author

Juri-Stepan Gerasimov, Jul 31 2025

Status

approved