From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit) Subject: Re: Sum of 4 Squares Date: 19 Jul 2001 01:45:20 GMT Newsgroups: sci.math Summary: Writing integers as sums of three or four squares In article , Stush wrote: >I'm looking for an algorithm no express any integer as the sum of four >square, i.e. > >Given n, find a,b,c,d such that >n = a^2 + b^2 + c^2 + d^2 > >Thanks See my paper with Michael Rabin, ``Randomized algorithms in number theory'', Commun. Pure and Appl. Math. 39 (1986), S239--S256, which gives an efficient algorithm. Jeffrey Shallit, Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada shallit@graceland.uwaterloo.ca URL = http://www.math.uwaterloo.ca/~shallit/ ============================================================================== From: alpertron@hotmail.com (Dario Alpern) Subject: Re: Number = Sum of squares Date: 10 Oct 2001 17:44:53 -0700 Newsgroups: sci.math alpertron@hotmail.com (Dario Alpern) wrote in message news:<1abc6a46.0109251419.e8249fb@posting.google.com>... > Hello all, > > I've just added a new feature to my ECM Online Factorization > Calculator that shows a decomposition of the number input by the user > in a sum of up to four squares. > > For example, the number > 54637856487946327819463278149637281496327814963278196437819654 can be > written as a^2 + b^2 + c^2 + d^2 where > > a = 6 108077 345747 128026 678719 165288 > b = 3 132268 970255 734978 111786 108799 > c = 2 731336 010938 625315 377818 001553 > d = 240712 109458 586493 590653 571750 > > The address is: > > http://www.alpertron.com.ar/ECM.HTM > When a number does not have the form 4^a * (8*m+7) (where a>=0), it can be expressed as a sum of three squares. Now the applet is able to show the sum of three squares. Using the same example shown above, the number can be written as a^2 + b^2 + c^2 where: a = 6 168255 775036 150097 322585 356374 b = 4 073140 947926 981706 465481 896717 c = 117 Best regards, Darío Alejandro Alpern Buenos Aires - Argentina http://www.alpertron.com.ar/ENGLISH.HTM