productdigits

productdigits.py

#!/usr/bin/python
import math

MAX_N = int(10e9)

max_prime = int(math.sqrt(MAX_N)) + 1

is_prime = [1]*(max_prime)
is_prime[0] = 0
is_prime[1] = 0

primes = []

for i in range(max_prime):
	if not is_prime[i]: continue
	primes += [i]
	for j in range(int(max_prime / i)):
		if i*j < max_prime:
			is_prime[i*j] = 0

def factorize(N):
	if N == 1: return []
	for p in primes:
		if (N % p == 0):
			return [p] + factorize(N / p)
	return [N]

def num_factors(f, factors):
	return sum(1 for _f in factors if _f == f)

powers = {} # powers of {2, 3} less than 10
for p in [2, 3, 4, 6, 8, 9]:
	fs = factorize(p)
	powers[p] = (num_factors(2, fs), num_factors(3, fs))

ms_memo = {}
def minimal_sequence(num_2s, num_3s):

	args = (num_2s, num_3s)
	if args in ms_memo:
		return ms_memo[args]

	candidates = set()

	for n in powers:
		req_2, req_3 = powers[n]
		if num_2s >= req_2 and num_3s >= req_3:
			candidates.add((n,) + minimal_sequence(num_2s - req_2, num_3s - req_3))

	if len(candidates) == 0:
		return ()

	def num_from_candidate(c):
		return int(''.join(map(str, c)))

	ms_memo[args] = min((num_from_candidate(c), c) for c in candidates)[1]
	return ms_memo[args]

def getXNumber(N):
	factors = factorize(N)
	num_2s = num_factors(2, factors)
	num_3s = num_factors(3, factors)
	big_factors = tuple(f for f in factors if f not in [2, 3])

	for c in big_factors:
		if int(c) >= 10:
			return "-1"

	factors = big_factors + minimal_sequence(num_2s, num_3s)

	return ''.join(map(str, sorted(factors)))