code.kerkeslager.com Git - sandbox/blob - factorization.py

   1 #!/usr/bin/env python
   2
   3 def getNewPairs(depth,a,b):
   4         m = 2**depth
   5
   6         if a == b:
   7                 return [(a,b),(a,b + m),(a + m,b + m)]
   8
   9         return [(a,b),(a,b + m),(a + m,b),(a + m,b + m)]
  10
  11 def lastDigits(number,depth):
  12         return number & (2**depth - 1)
  13
  14 def multiply(a,b):
  15         return a * b
  16
  17 def factor(number, pairs = [(0,0)], depth=0):
  18         test = lastDigits(number,depth)
  19
  20         newpairs = []
  21
  22         for pair in pairs:
  23                 product = multiply(*pair)
  24
  25                 if product == number:
  26                         return pair
  27
  28                 elif lastDigits(product,depth) == test:
  29                         newpairs += getNewPairs(depth,*pair)
  30
  31         return factor(number,newpairs,depth + 1)
  32
  33 if __name__ == '__main__':
  34         print factor(611951 * 611953)