Post Reply 
Sum of Two Squares
08-17-2019, 01:35 PM
Post: #1
Sum of Two Squares
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/h...f-two.html
Visit this user's website Find all posts by this user
Quote this message in a reply
08-17-2019, 07:05 PM
Post: #2
RE: Sum of Two Squares
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?
Find all posts by this user
Quote this message in a reply
08-18-2019, 05:27 PM
Post: #3
RE: Sum of Two Squares
I'll check it out and maybe give it a shot.
Visit this user's website Find all posts by this user
Quote this message in a reply
08-20-2019, 05:25 AM
Post: #4
RE: Sum of Two Squares
(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)}}
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)