|
%I #15 May 15 2017 11:32:34
%S 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,
%T 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,
%U 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
%N Least number of squares which add to -1 mod n.
%C Pfister proved that a(p) <= 2 for all primes p; then a(p) is called the stufe of the field Z/pZ.
%C 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.
%D Albert Pfister, Zur Darstellung von -1 Als Summe von Quadraten in einem Korper, J. London Math. Society, 40 (1965), pp. 159-165.
%D A. R. Rajwade, Squares, Cambridge Univ. Press, 1983.
%H Charles R Greathouse IV, <a href="/A227781/b227781.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) <= A002828(n-1) <= 4.
%F a(n) = 1 if and only if n > 1 is in A008784. a(4n) >= 3 for all n.
%e a(3) = 2: 1^2 + 1^2 = -1 mod 3.
%e a(15) = 2: 2^2 + 5^2 = -1 mod 15.
%o (PARI) isA008784(n)=if(n%2==0, if(n%4, n/=2, return(0))); n==1||vecmax(factor(n)[, 1]%4)==1
%o 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
%Y Cf. A008784, A002828.
%K nonn
%O 1,3
%A _Charles R Greathouse IV_, Jul 31 2013
|
