|
%I #30 Jun 14 2017 05:12:30
%S 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,
%T 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,
%U 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
%N Every element of Z/nZ can be expressed as a sum of no more than a(n) squares.
%H Matthew Conroy, <a href="/A288677/b288677.txt">Table of n, a(n) for n = 2..10000</a>
%H Charles Small, <a href="http://www.jstor.org/stable/2318299">Waring's problem mod n</a>, Amer. Math. Monthly 84 (1977), no. 1, 12--25.
%F 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.
%e 0^2 = 0 and 1^2 = 1 mod 2, so each element of Z/2Z is a square, so a(2)=1;
%e 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.
%t 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];
%t Table[a[n], {n, 2, 140}] (* _Jean-François Alcover_, Jun 13 2017 *)
%o (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),","))
%Y Cf. A287286.
%K nonn
%O 2,2
%A _Matthew Conroy_, Jun 13 2017
|
