login
A227781
Least number of squares which add to -1 mod n.
4
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,3
COMMENTS
Pfister proved that a(p) <= 2 for all primes p; then a(p) is called the stufe of the field Z/pZ.
Conjecture: a(n) = 4 if and only if n is divisible by 8 and a(n) = 3 if and only if n is 4 mod 8. Together with A008784 this would completely define the sequence.
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
FORMULA
a(n) <= A002828(n-1) <= 4.
a(n) = 1 if and only if n > 1 is in A008784. a(4n) >= 3 for all n.
EXAMPLE
a(3) = 2: 1^2 + 1^2 = -1 mod 3.
a(15) = 2: 2^2 + 5^2 = -1 mod 15.
PROG
(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)-1), t>>n); new=bitor(new, t)); k++; cur=new); k
CROSSREFS
Sequence in context: A358638 A236855 A244232 * A366294 A351441 A254761
KEYWORD
nonn
AUTHOR
STATUS
approved