Sunday, October 20, 2019

HP 12C: Finding Two Factors of an Integer

HP 12C:  Finding Two Factors of an Integer 



Introduction

This program finds two factors of the integer N, where one of the factors is close to, but not equal to √N as possible. 

Let X and Y be positive integers where:

(I)
N = B^2 - A^2

By the difference of squares:

(II)
N = (B - A) * (B + A)

The program tests every integer higher than √N.  Let B = int(√N) + 1.   If A = N - B^2 is an integer, the search stops.  The program uses the equation (II) above and places the results on the stack as such:

Y Stack:  B + A   // the program pauses to show this result
X Stack:  B - A

Program:
(Step ##: key code: key)
01:  44, 0:  STO 0
02:  43, 21: √
03:  43, 25:  INTG
04:  1:  1
05:  40:  +
06:  44, 1: STO 1
07:  2:   2
08:  21:  y^x
09:  45, 0:  RCL 0
10:  30:  -
11:  43, 21:  √
12:  44, 2:   STO 2
13:  43, 24:  FRAC
14:  43, 35:  X=0
15:  43, 33, 20:  GTO 20
16:  1:   1
17:  44, 40, 1:  STO+1
18:  45, 1:  RCL 1
19:  43, 33, 07:  GTO 07
20:  45, 1:  RCL 1
21:  45, 2:  RCL 2
22:  40:   +
23:  43, 31:  PSE
24:  45, 1:  RCL 1
25:  45, 2:  RCL 2
26:  30:  -
27:  43, 33, 00:  GTO 00

Examples:
n = 22356 = 162 * 138

n = 667 = 29 * 23

n = 4120 = 206 * 20

n = 144 = 18 * 8
(remember, factors close to √n as possible, but not the square root)

n = 97 = 97 * 1
(prime number)

Eddie

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.