(12C) Finding Two Factors Close to N
10-20-2019, 03:10 PM
Post: #1
 Eddie W. Shore Senior Member Posts: 1,146 Joined: Dec 2013
(12C) Finding Two Factors Close to N
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
10-20-2019, 11:02 PM
Post: #2
 Albert Chan Senior Member Posts: 1,243 Joined: Jul 2018
RE: (12C) Finding Two Factors Close to N
(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