+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (12C) Finding Two Factors Close to N (/thread-13829.html)
(12C) Finding Two Factors Close to N - Eddie W. Shore - 10-20-2019 03:10 PM
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 00Examples:
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/hp-12c-finding-two-factors-of-integer.html
RE: (12C) Finding Two Factors Close to N - Albert Chan - 10-20-2019 11:02 PM
(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-11374-post-103957.html#pid103729