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

Question

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

I give you a hint: [Sieve algorithm](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) this will save your life with this challange of Projecteuler and many others there. If you found it difficult, i can post my answer to this question using `Sieve algorithm`. Otherwise, try it with yourself, this is the best practice. Also, remember one thing: Projecteuler's question must be solved within less than one minute. If not, you must change your approach/algorithm/manner of thinking. — Chiheb Nexus, May 06 '17 at 01:55
@ChihebNexus the sieve is good, but understanding why this implementation of a different approach doesn't work is even better. Also there is no limit of time of project Euler's problems. If one want to use a brute force approach, why not? — njzk2, May 06 '17 at 02:10

score 4 · Accepted Answer · answered May 06 '17 at 02:09

4

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).

answered May 06 '17 at 02:09

njzk2

38,969
7
69
107

Oh ok. Other than that, the implementation is correct? – Liam Wilson May 06 '17 at 02:35
there is room for optimization, but it looks like a valid implementation of fermat's factorization. you'll have to find a better square root, though. – njzk2 May 06 '17 at 04:03
(see http://stackoverflow.com/questions/30490439/how-to-take-square-root-of-large-numbers-in-python) – njzk2 May 06 '17 at 04:03

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

1 Answers1