From 249411c080477350129b388cb544c1476c844f96 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Tue, 6 Jul 2010 02:42:40 -0400 Subject: [PATCH] Weird factorization algorithm. --- factorization.py | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 factorization.py diff --git a/factorization.py b/factorization.py new file mode 100644 index 0000000..b08a95f --- /dev/null +++ b/factorization.py @@ -0,0 +1,34 @@ +#!/usr/bin/env python + +def getNewPairs(depth,a,b): + m = 2**depth + + if a == b: + return [(a,b),(a,b + m),(a + m,b + m)] + + return [(a,b),(a,b + m),(a + m,b),(a + m,b + m)] + +def lastDigits(number,depth): + return number & (2**depth - 1) + +def multiply(a,b): + return a * b + +def factor(number, pairs = [(0,0)], depth=0): + test = lastDigits(number,depth) + + newpairs = [] + + for pair in pairs: + product = multiply(*pair) + + if product == number: + return pair + + elif lastDigits(product,depth) == test: + newpairs += getNewPairs(depth,*pair) + + return factor(number,newpairs,depth + 1) + +if __name__ == '__main__': + print factor(611951 * 611953) -- 2.20.1