Project Euler P.88

• 2x3 , 2+3이 있을 때 product와 sum의 차이는 1이기 때문에 양쪽에 각각 1을 곱하고 더하면 1x2x3 == 1+2+3 이된다. 즉 product와 sum이 같은 3개의 숫자를 구할 수 있다.
• 수를 계속 증가시키면서 factorization한 후 product와 sum의 차이만큼 양쪽에 1을 더하고 곱하면 product와 sum이 같은 set을 구할 수 있다.

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import math
import operator
"""Project Euler Problem 88"""

d = {}
c = set(range(2, 12000+1))

def factorizations(n):
  answer = []
  def sub(n, factor=2, factors=[]):
    for x in range(factor, int(math.sqrt(n))+1):
      if n % x == 0:
        sub(n/x, x, factors + [x])      
    answer.append(factors + [n])
  sub(n)
  return answer

def func(l):
  s = reduce(operator.add, l)
  m = reduce(operator.mul, l)
  length = len(l) + (m-s)
  if length not in d.keys():
    d[length] = m
    c.discard(length)
    print '%6d %6d %s' % (len(c), length, m)

def solve(limit=12000):
  n = 4
  while c:
    map(func, factorizations(n))
    n += 1

  return reduce(operator.add, set( [d[x] for x in range(2, limit+1)] ))
  
if __name__ == '__main__':
  solve()