login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Cf. A008784, A002828.

Sequence in context: A324920 A236855 A244232 * A254761 A227552 A205003

Adjacent sequences:  A227778 A227779 A227780 * A227782 A227783 A227784

KEYWORD

nonn

AUTHOR

Charles R Greathouse IV, Jul 31 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 13:31 EST 2019. Contains 329230 sequences. (Running on oeis4.)