HP Forums

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

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

(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