A366418 Number of distinct integers of the form (x^n + y^n) mod n.

1, 2, 3, 3, 5, 6, 7, 3, 5, 10, 11, 9, 13, 14, 15, 3, 17, 6, 19, 9, 15, 22, 23, 9, 13, 26, 5, 21, 29, 30, 31, 3, 33, 34, 35, 9, 37, 38, 39, 9, 41, 18, 43, 33, 25, 46, 47, 9, 19, 10, 51, 30, 53, 6, 25, 21, 57, 58, 59, 27, 61, 62, 25, 3, 65, 66, 67, 39, 69, 70, 71, 9, 73, 74, 39

Offset: 1

Author

Albert Mukovskiy, Oct 11 2023

Keywords

• nonn

Comments

a(p) = p when p is prime. It appears that a(n) stabilizes for the subsequences n = k^m for each fixed k > 1 at large enough m.

a(n) = n if there are more than n/2 distinct integers x^n mod n. - David A. Corneth, Oct 16 2023

Links

• David A. Corneth, PARI program

Crossrefs

Cf. A121278, A366419, A195637.

Programs

PARI

{ a(n) = my(S,t); S=Set(); for(x=0, n-1, for(y=x, n-1, t=lift(Mod(x,n)^n+Mod(y,n)^n); S=setunion(S,[t]); ); ); #S }

PARI

a(n) = #setbinop((x,y)->Mod(x,n)^n+Mod(y,n)^n, [0..n-1]); \\ Michel Marcus, Oct 12 2023

PARI

See PARI link \\ David A. Corneth, Oct 16 2023