 Sum of Two Squares - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: HP Prime Software Library (/forum-15.html) +--- Thread: Sum of Two Squares (/thread-13468.html) Sum of Two Squares - Eddie W. Shore - 08-17-2019 01:35 PM Given a positive integer n, can we find two non-negative integers x and y such that: n = x^2 + y^2 The program presented here is the use of iterations to find all possible pairs which fit n = x^2 + y^2. Some integers do not have representations, others have more than one. The program will show all possible combinations. HP Prime Program SUM2SQ Code: ``` EXPORT SUM2SQ(n) BEGIN // EWS 2019-07-21 // breaking n into a sum of 2 squares LOCAL r,j,k,l; // we can more than 1 representation r:=IP((n/2)^0.5); l:={}; FOR j FROM 0 TO r DO k:=(n-j^2)^0.5; IF FP(k)==0 THEN l:=CONCAT(l, {STRING(j)+"^2 + "+ STRING(k)+"^2 = "+ STRING(n)}); END; END; RETURN l; END;``` Blog link: http://edspi31415.blogspot.com/2019/08/hp-prime-and-hp-41cdm-41l-sum-of-two.html RE: Sum of Two Squares - klesl - 08-17-2019 07:05 PM Very interesting :-) Another interesting topic in number theroy is Bézout's_identity https://en.wikipedia.org/wiki/Bézout's_identity Can you write a program for this also? RE: Sum of Two Squares - Eddie W. Shore - 08-18-2019 05:27 PM I'll check it out and maybe give it a shot. RE: Sum of Two Squares - Eddie W. Shore - 08-20-2019 05:25 AM (08-17-2019 07:05 PM)klesl Wrote:  Very interesting :-) Another interesting topic in number theroy is Bézout's_identity https://en.wikipedia.org/wiki/Bézout's_identity Can you write a program for this also? Here is the Bezout program: this program returns the gcd of two integers a and b, and all of the possible integer solutions that fit a*x + b*y = d, with in a given range [-m, m]: Code: ```EXPORT BEZOUT(a,b,m) BEGIN // integers a, b, range -m to m // 2019-08-19 EWS LOCAL d,l,k,x,y; d:=gcd(a,b); l:={}; FOR k FROM −m TO m DO x:=k; y:=(d-a*x)/b; IF FP(y)==0 THEN l:=CONCAT(l,(x,y)); END; END; RETURN {d,l}; END;``` Output: { gcd, list of (x,y) pairs } Example: a = 18, b = 45, m = 20, find all solutions within the range [-20, 20]: BEZOUT(18, 45, 20): {9, {(-17, 7), (-12,5), (-7,3), (-2,1), (3,-1), (8,-3), (13,-5), (18,-7)}}