(12C) Finding Two Factors Close to N

[Eddie W. Shore]

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

Code:


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)


Blog post: http://edspi31415.blogspot.com/2019/10/h...teger.html

[Albert Chan]

(10-20-2019 03:10 PM)Eddie W. Shore Wrote:  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.

I think you meant the program test integer C = A+B, A+B+1, A+B+2, ...
If C^2 - N is a square, then stop

Using your example, N = 22356

C = int(√N) + 1 = 150
C^2 - N = 144 = 12^2

→ N = 150^2 - 12^2 = (150 + 12) * (150 - 12) = 162 * 138

Thomas Kleem also posted Fermat Factorization code for HP-12C, but only for odd N
https://www.hpmuseum.org/forum/thread-11...#pid103729