sumsqint

Finds all distinct ways of writing a number as the sum of squares, i.e. solve x^2+y^2=n for 0<=x<=y.

Description

Example:

   sumsqint(1) % returns [0,1]
   sumsqint(65) % returns [1,8;4,7]

sumsqint can work with large numbers if they are factored, e.g. solve x^2+y^2=(25e6)^2:
   sumsqint(repmat(factor(25e6),1,2)) % returns 9x2 array

sumsqint works with variable precision integers if you have John D'Errico's Variable Precision Integer toolbox (20 July 2009 update) - see links below.

   sumsqint(vpi(5)^100) % returns 51x2 vpi array
   sumsqint(vpi(65)^100) % returns 5101x2 vpi array

The algorithm uses Gaussian integer factorization. See the help for more details.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Variable Precision Integer Arithmetic

• MATLAB release: MATLAB 7.8 (R2009a)

[John D'Errico]

A nifty piece of code. Well written. Good help. Fast - even on my old cpu.

tic,xy = sumsqint(vpi(51)^32);toc
Elapsed time is 3.341508 seconds.

xy
xy =
                    0 2094704750199298376445300801
     30716516552930718230081601 2094479526306800294009550720
    180465099249163605704475624 2086916466574667319894682335
    211048005566589191194875615 2084045760019167609213236376
    389810107080067581524800449 2058114688477231401347749200
    419948158440662717915958480 2052177266887488219864204351
    595187985793527352363191624 2008367310049272061252396065
    624574464800990440465293345 1999423599047000686612625976
    794508588038500176810750399 1938180614401189862809267680
    822844426109404969034724960 1926321634859606979062120001
    985743411858493353621318024 1848268897234675038039971295
   1012740232867550772089860575 1833615338951679921429565176
   1141312248313811332042623120 1756472129683923585457907649
   1166946244920716396566413249 1739547197397341212272914160
   1312474653765815584332588255 1632543498265760609883402024
   1336272971277049795744294824 1613121984458060091449141025
   1470279898076299222086296640 1492000339081815417640023999