Based on that I wrote this function. It takes in c and number of steps, then it iterates down n and uses gcd to attempt to find the factors.
def goDownSteps(c, steps=2): e, n, d, x, a, b = rowForAB(1, c) bb = b for i in range(steps): ee, nn, dd, xx, aa, bb = rowNegX(n, -(2 * i * n + x), bb) g = math.gcd(c, bb) if g != 1: print(g, c / g) break
Unfortunately it's still way too slow.
You mean 145, 533?
That's what rowX already does.
>>rowForAB(1, 145)(1, 61, 12, 11, 1, 145)>>> rowX(61, (2 * 61 + 11), 145)(1, 61, 278, 133, 145, 533)
The code for rowX is:
def rowX(n, x, a): b = a + 2x + 2n c = ab d = int(math.floor(math.sqrt(c))) e = int(c - dd) n = int(((a + b)/2) - d) x = int(d - a) return (e, n, d, x, a, b)
I've been thinking about what f means and the (-e, n) records and it's quite obvious.
I'm just writing this as I'm thinking loud, but of course (-e, n) records contain the same info, but with d + 1, n - 1 etc.
It's because it's the big square (d + 1)^2.
e is the remainder after removing d^2 from c. So negative e is the "remainder" after removing the upper square (d + 1)^2, or rather the number of empty parts.
n - 1 makes sense because we are now 1 square closer to the n we need to find the factors. Increase of d again makes sense because d represents the square.
Same as x + 1 because n is now (n - 1) so we need to increase x by 1 to maintain the same number (n + x).
I don't see any obvious way to make use of f.
So if we extend the idea of f, we can do
e - 3*(2 * d + 3) which should give us n - 2, d + 2, x + 2.
e - 4*(2 * d + 4) which should give us n - 3, d + 3, x + 3 etc..
This is because we are increasing the squares. Note though: This isn't how we can factorize as this is the original fermats factorization.
Wait, I think that's wrong. e - 3(2 * d + 3) should give us n - 3, d + 3, x + 3 since f = e - 1(2*d + 1).
Well yeah, but the e - 3(2d + 3), e- 4*(2 * d + 4) etc is the slow, original method.