HP Prime and HP 41C/DM 41L: Sum of Two Squares
Introduction
Given a positive integer n, can we find two non-negative integers x and y such that:
n = x^2 + y^2
(x and y can be 0, n is assumed to be greater than 0)
There are several theorems and lemmas that are connected to this famous problem. As a point of interest, I will briefly describe them here.
1. n does not have a representation (n can't be written as x^2 + y^2) if any of n's prime factors is congruent to 3 mod 4 and is raised to an odd power.
2. If n has a representation, then for an integer k, k^2*n also has a representation.
3. If n is prime and congruent to 1 mod 4, then n has a representation. (n has the form of n = 4w + 1 for some non-negative integer w).
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
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;
HP 41C/DM 41L Program SUMSQRS
Registers used:
R00 = n
R01 = counter
R02 = temporary
01 LBL T^SUMSQRS
02 FIX 0
03 STO 00
04 2
05 /
06 SQRT
07 INT
08 1000
09 /
10 STO 01
11 LBL 00
12 RCL 00
13 RCL 01
14 INT
15 X↑2
16 -
17 SQRT
18 STO 02
19 FRC
20 X=0?
21 GTO 01
22 GTO 02
23 LBL 01
24 RCL 01
25 INT
26 T^X =
27 ARCL X
28 AVIEW
29 STOP
30 RCL 02
31 T^Y =
32 ARCL X
33 AVIEW
34 STOP
35 LBL 02
36 ISG 01
37 GTO 00
38 T^END
39 VIEW
40 FIX 4
41 RTN
Examples
Example 1: n = 325
325 = 1^2 + 18^2
325 = 6^2 + 17^2
325 = 10^2 + 15^2
Example 2: n = 530
530 = 1^2 + 23^2
530 = 13^2 + 19^2
Source:
Dudley, Underwood. "Elementary Number Theory" 2nd Ed. Dover Publications: New York. 1978. ISBN 978-0-486-46931-7
All original content copyright, © 2011-2019. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.
Introduction
Given a positive integer n, can we find two non-negative integers x and y such that:
n = x^2 + y^2
(x and y can be 0, n is assumed to be greater than 0)
There are several theorems and lemmas that are connected to this famous problem. As a point of interest, I will briefly describe them here.
1. n does not have a representation (n can't be written as x^2 + y^2) if any of n's prime factors is congruent to 3 mod 4 and is raised to an odd power.
2. If n has a representation, then for an integer k, k^2*n also has a representation.
3. If n is prime and congruent to 1 mod 4, then n has a representation. (n has the form of n = 4w + 1 for some non-negative integer w).
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
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;
HP 41C/DM 41L Program SUMSQRS
Registers used:
R00 = n
R01 = counter
R02 = temporary
01 LBL T^SUMSQRS
02 FIX 0
03 STO 00
04 2
05 /
06 SQRT
07 INT
08 1000
09 /
10 STO 01
11 LBL 00
12 RCL 00
13 RCL 01
14 INT
15 X↑2
16 -
17 SQRT
18 STO 02
19 FRC
20 X=0?
21 GTO 01
22 GTO 02
23 LBL 01
24 RCL 01
25 INT
26 T^X =
27 ARCL X
28 AVIEW
29 STOP
30 RCL 02
31 T^Y =
32 ARCL X
33 AVIEW
34 STOP
35 LBL 02
36 ISG 01
37 GTO 00
38 T^END
39 VIEW
40 FIX 4
41 RTN
Examples
Example 1: n = 325
325 = 1^2 + 18^2
325 = 6^2 + 17^2
325 = 10^2 + 15^2
Example 2: n = 530
530 = 1^2 + 23^2
530 = 13^2 + 19^2
Source:
Dudley, Underwood. "Elementary Number Theory" 2nd Ed. Dover Publications: New York. 1978. ISBN 978-0-486-46931-7
All original content copyright, © 2011-2019. Edward Shore. Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited. This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.
