Why is this an incorrect implementation of Fermat Factorization?
I am currently working through Project Euler and this was my attempt (in Python) on problem 3. I ran and gave it about 30 minutes. After that I looked at the numbers under the "sum". I found several questions: some of these numbers were even, and therefore not the first, and some of those numbers were not even the correct factors of n. Of course, they were only disabled by 0.000001 (usually the division would give x.99999230984 or whatever). The number that I eventually stopped at was 3145819243.0.
Can anyone explain why these errors are occurring?
EDIT: My interpretation of the theorem was basically that with the permutation of variables, you could solve for x with a square root of n + y ^ 2, and y would be roughly coercive until it becomes an integer. After that, the actual prime factor will be x + y.
Here is my code.
import math
n = int(600851475143)
y = int(1)
while y >= 1:
if math.sqrt(n + (y**2)).is_integer():
x = math.sqrt(n + (y**2))
print "x"
print x
print "sum"
print x + y
if x + y > (600851475142/2):
print "dead"
else:
print "nvm"
y = y + 1
source to share
Typical problem with high precision numbers and floating point.
When you go to y = 323734167
, you calculate math.sqrt(n + y**2)
which is math.sqrt(104804411734659032)
.
This 3.23735095000000010811308548429078847808587868214170702... × 10^8
is according to wolfram alpha i.e. not an integer, but 323735095.0
according to python.
As you can see, python has no precision to see .00000001...
.
Instead of testing, is_integer
you can check the square of the result:
> 323735095 ** 2
=> 104804411734659025
and see if it matches the input (it is not, input 104804411734659032
, off at 7).
source to share