CODEWITHSUNDEEP
pythonmathfactorization
Liam Wilson
Liam Wilson

Reputation: 188

Why is this an incorrect implementation of Fermat's Factorization?

I'm currently working through Project Euler, and this was my attempt (in Python) at problem 3. I ran this and let it for roughly 30 minutes. After this, I looked at the numbers under "sum". I found several issues: some of these numbers were even, and thus not prime, and some of these numbers weren't even proper factors of n. Granted, they were only off by 0.000001 (usually division yielded x.99999230984 or whatever). The number I eventually stopped at was 3145819243.0.

Can anyone explain why these errors occur?

EDIT: My interpretation of the theorem was basically that, with rearranging of variables, you could solve for x with the square root of n + y^2, and y would be bruteforced until it was an integer. After this, the actual prime factor would 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

Upvotes: 3

Views: 266

Answers (1)

njzk2
njzk2

Reputation: 39406

Typical issue with big number and floating points precision.

When you get to y = 323734167, you compute math.sqrt(n + y**2) which is math.sqrt(104804411734659032).

This is 3.23735095000000010811308548429078847808587868214170702... × 10^8 according to wolfram alpha, i.e. not an integer, but 323735095.0 according to python.

As you can see, python does not have the precision to see the .00000001....

Instead of testing is_integer, you can test the square of the result:

 > 323735095 ** 2
=> 104804411734659025

and see if it matches the input (it doesn't, the input is 104804411734659032, off by 7).

Upvotes: 4

Related Questions