c A151925 implicit integer(a-o) implicit double precision(p-z) integer ivec(5) c set n (>= 2) do 300 n=2,1000 c write(*,*)"n = ",n ans=6 xn=n xsq=dsqrt(xn) nsq=xsq c write(*,*)"n,nsq",n,nsq do 1 i1=1,nsq m1=i1**2 do 2 i2=i1,nsq m2=m1+i2**2 if(m2.gt.n)goto 1 call gcd1(i1,i2,k1,k2,g12) c write(*,*)"i1,i2,m2,gcd ",i1,i2,m2,g12 if(m2.lt.n)goto 20 c have n = i1^2+i2^2 if(g12.gt.1)goto 2 c success if(ans.le.2)goto 2 ans=2 c write(*,*)"got 2 ",n,i1,i2 ivec(1)=i1 ivec(2)=i2 c can abort since cannot beat 2! goto 299 20 continue do 3 i3=i2,nsq m3=m2+i3**2 if(m3.gt.n)goto 2 call gcd1(g12,i3,k1,k2,g13) if(m3.lt.n)goto 30 c have n = i1^2+i2^2+i3^2 if(g13.gt.1)goto 3 c success if(ans.le.3)goto 3 ans=3 c write(*,*)"got 3 ",n,i1,i2,i3 ivec(1)=i1 ivec(2)=i2 ivec(3)=i3 goto 2 30 continue do 4 i4=i3,nsq m4=m3+i4**2 if(m4.gt.n)goto 3 call gcd1(g13,i4,k1,k2,g14) if(m4.lt.n)goto 40 c have n = i1^2+i2^2+i3^2+i4^2 if(g14.gt.1)goto 4 c success if(ans.le.4)goto 4 ans=4 c write(*,*)"got 4 ",n,i1,i2,i3,i4 ivec(1)=i1 ivec(2)=i2 ivec(3)=i3 ivec(4)=i4 goto 3 40 continue c so need 5 for this branch c is the residue a square? m5=n-m4 xm5=m5 x5=dsqrt(xm5)+1.0d-6 i5=x5 if(i5**2.lt.m5)goto 4 c success if(ans.le.5)goto 4 ans=5 c write(*,*)"got 5 ",n,i1,i2,i3,i4,i5 ivec(1)=i1 ivec(2)=i2 ivec(3)=i3 ivec(4)=i4 ivec(5)=i5 4 continue 3 continue 2 continue 1 continue c wrap up this n 299 continue write(*,100)n,ans,(ivec(i),i=1,ans) 100 format(7i7) 300 continue stop end subroutine gcd1(u,v,u1,u2,u3) c given integers u,v this finds u1,u2,u3 s.t. c u.u1 + v.u2 = u3 = gcd(u,v) c and u3>0 c ref Knuth 2 p. 302 c checked 11/87 integer u,v,u1,u2,u3,v1,v2,v3,t1,t2,t3,q,su,sv su=1 sv=1 if(u.ge.0)goto 2 su=-1 2 if(v.ge.0)goto 3 sv=-1 3 u1=1 u2=0 u3=u*su v1=0 v2=1 v3=v*sv 1 if(v3.eq.0) goto 4 q=u3/v3 t1=u1-v1*q t2=u2-v2*q t3=u3-v3*q u1=v1 u2=v2 u3=v3 v1=t1 v2=t2 v3=t3 goto 1 4 u1=su*u1 u2=sv*u2 return end