A288677 Every element of Z/nZ can be expressed as a sum of no more than a(n) squares.

1, 2, 3, 2, 2, 2, 4, 3, 2, 2, 3, 2, 2, 2, 4, 2, 3, 2, 3, 2, 2, 2, 4, 2, 2, 3, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 3, 2, 2, 4, 3, 2, 2, 3, 2, 3, 2, 4, 2, 2, 2, 3, 2, 2, 3, 4, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4, 3, 2, 2, 3, 2, 2, 2, 4, 2, 3, 2, 3, 2, 2, 2, 4, 2, 3, 3, 3

Offset: 2

Author

Matthew Conroy, Jun 13 2017

Keywords

• nonn

Examples

			0^2 = 0 and 1^2 = 1 mod 2, so each element of Z/2Z is a square, so a(2)=1;
0^2 = 0, 1^2 = 2^2 = 1 mod 3, so 2 = 1^2 + 1^2 requires two squares to sum to 2, so a(3)=2.
		

Links

• Matthew Conroy, Table of n, a(n) for n = 2..10000
• Charles Small, Waring's problem mod n, Amer. Math. Monthly 84 (1977), no. 1, 12--25.

Crossrefs

Cf. A287286.

Programs

Mathematica

a[n_] := Which[n == 2, 1, Mod[n, 4] != 0 && AllTrue[Select[Divisors[n] // Sqrt, IntegerQ], Mod[#, 4] == 1&], 2, Mod[n, 8] != 0, 3, True, 4];
Table[a[n], {n, 2, 140}] (* Jean-François Alcover, Jun 13 2017 *)

PARI

c(n) = A=factor(n);ok=1;for(i=1,matsize(A)[1],if(A[i,1]%4==3&&A[i,2]>1,ok=0));return(ok); wn(n) = if(n==2,1,if(n%4>0&&c(n)==1,2,if(n%8>0,3,4))); for(ii=2,140,print1(wn(ii),","))

Formula

From Small's paper, theorem 3.1: a(n)=1 if n=2; else a(n)=2 if n != 0 mod 4 and p^2|n implies p=1 mod 4; else a(n)=3 if n!=0 mod 8; else a(n)=4.