Saturday, August 17, 2019

HP Prime and HP 41C/DM 41L: Sum of Two Squares

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.