A289559 Number of modulo n residues among sums of two fourth powers.

1, 2, 3, 3, 3, 6, 7, 3, 7, 6, 11, 9, 10, 14, 9, 3, 13, 14, 19, 9, 21, 22, 23, 9, 11, 20, 19, 21, 22, 18, 31, 6, 33, 26, 21, 21, 37, 38, 30, 9, 41, 42, 43, 33, 21, 46, 47, 9, 43, 22, 39, 30, 53, 38, 33, 21, 57, 44, 59, 27, 61, 62, 49, 11, 30, 66, 67

Offset: 1

Author

Jon E. Schoenfield, Jul 08 2017

Keywords

• nonn
• mult

Comments

Conjecture: the only primes p for which a(p) < p are 5, 13, 17, 29. - Robert Israel, Jul 09 2017

Conjecture is true: see Math Overflow link. - Robert Israel, Apr 01 2020

Examples

			a(7) = 7 because (j^4 + k^4) mod 7, where j and k are integers, can take on all 7 values 0..6; e.g.:
   (0^4 + 0^4) mod 7 = ( 0 +  0) mod 7 =  0 mod 7 = 0;
   (0^4 + 1^4) mod 7 = ( 0 +  1) mod 7 =  1 mod 7 = 1;
   (1^4 + 1^4) mod 7 = ( 1 +  1) mod 7 =  2 mod 7 = 2;
   (1^4 + 2^4) mod 7 = ( 1 + 16) mod 7 = 17 mod 7 = 3;
   (2^4 + 2^4) mod 7 = (16 + 16) mod 7 = 32 mod 7 = 4;
   (1^4 + 3^4) mod 7 = ( 1 + 81) mod 7 = 82 mod 7 = 5;
   (2^4 + 3^4) mod 7 = (16 + 81) mod 7 = 97 mod 7 = 6.
a(16) = 3 because (j^4 + k^4) mod 16 can take on only the three values 0, 1, and 2. (This is because j^4 mod 16 = 0 for all even j and 1 for all odd j.)
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Mathematics Overflow, Does the expression x^4+y^4 take on all values in Z/pZ (see answer by J. Silverman)

Crossrefs

Cf. A155918 (gives number of modulo n residues among sums of two squares).

Programs

Maple

f1:= proc(n) option remember; local S;
    S:= {seq(x^4 mod n, x=0..n-1)};
  nops({seq(seq(S[i]+S[j] mod n,i=1..j),j=1..nops(S))});
end proc:
f:= proc(n) local t;
mul(f1(t[1]^t[2]), t = ifactors(n)[2])
end proc:
map(f, [$1..100]); # Robert Israel, Jul 09 2017

Mathematica

f1[n_] := f1[n] = Module[{S = Table[Mod[x^4, n], {x, 0, n-1}] // Union}, Table[Mod[S[[i]] + S[[j]], n], {j, 1, Length[S]}, {i, 1, j}] // Flatten // Union // Length];
f[n_] := Module[{p, e}, Product[{p, e} = pe; f1[p^e], {pe, FactorInteger[n]}]];
Array[f, 100] (* Jean-François Alcover, Jul 30 2020, after Maple *)

PARI

a(n) = #Set(vector(n^2, i, ((i%n)^4 + (i\n)^4) % n)); \\ Michel Marcus, Jul 08 2017