A227781 Least number of squares which add to -1 mod n.
0, 1, 2, 3, 1, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2, 2, 4, 1, 1, 2, 3, 1, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2, 2, 4, 1, 1, 2, 3, 2, 2, 2, 4, 2, 1, 2, 3, 1, 2, 2, 4, 1, 2, 2, 3, 2, 2
Offset: 1
Keywords
Examples
a(3) = 2: 1^2 + 1^2 = -1 mod 3. a(15) = 2: 2^2 + 5^2 = -1 mod 15.
References
- Albert Pfister, Zur Darstellung von -1 Als Summe von Quadraten in einem Korper, J. London Math. Society, 40 (1965), pp. 159-165.
- A. R. Rajwade, Squares, Cambridge Univ. Press, 1983.
Links
- Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Programs
-
PARI
isA008784(n)=if(n%2==0, if(n%4, n/=2, return(0))); n==1||vecmax(factor(n)[, 1]%4)==1 a(n)=if(isA008784(n),return(n>1)); if(isprime(n), return(2)); if(n%8==0, return(4)); my(N, cur, new, k=1); for(i=1,n\2,cur=N=bitor(1<<(i^2%n),N)); while(!bittest(cur,n-1), new=0; for(i=1,n\2, t=cur<<(i^2%n); t=bitor(bitand(t,(1<
>n); new=bitor(new,t)); k++; cur=new); k
Comments