cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A227781 Least number of squares which add to -1 mod n.

Original entry on oeis.org

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

Views

Author

Keywords

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.

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.

Crossrefs

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

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.