I have a number N (integer 32 bits) that I need to "factor" into 1-16 product and sum parts. Let me explain:
- For $N = 256$, I want: $(16 \times 16)$
- For $N = 257$, I want: $(16 \times 16) + 1$
- For $N = 512$, I want: $(16 \times 16) \times 2$
- For $N = 530$, I want: $(16 \times 16 \times 2) + (2 \times 9)$
- For $N = 531$, I want: $(16\times 11 \times 3) + 3$
The minor number of sums are better, i.e., products should be preferred.
Is there a algorithm for this?
I've enclosed a brute-force Python algorithm, below. There are a few tricks that make the algorithm more efficient:
To find a minimal sum for $n$, find every $k<n$ that can be written as a product of factors less than 16. (It's enough to check that all of the prime factors are less than 16).
Use the following dynamic programming principle: if the minimal sum for $n$ includes $k$ as a term, then the other terms in the sum are the minimal sum for $n-k$. (You can cache the minimal sums if you plan to find the minimal sums for a lot of numbers.)
Return the combination of $k$, minimal_sum($n-k)$ with the fewest terms.
def minimal_sum(n) : best_sum = None if n == 0 : return [] if sum_cache.get(n) : return sum_cache[n] for summand in range(n,0,-1) : fs = factors(summand) if any([f > 16 for f in fs.keys()]) : continue other_factors = minimal_sum(n-summand) if best_sum is None or len(best_sum) > len(other_factors)+1 : best_sum = [summand] + other_factors if len(best_sum) == 1 : # short circuit sum_cache[n] = best_sum return best_sum sum_cache[n] = best_sum return best_sumdef factorize(n, limit=16, as_string=True) : """Write the number n as a product of factors less than limit.""" factor_map = factors(n) if any(x > limit for x in factor_map.keys()) : return None fs = [] for f in sorted(factor_map.keys()) : fs += [f] * factor_map[f] ret = [] while fs : k = fs.pop() term = [k] while fs and reduce(lambda a,b:a*b, term, fs[0]) < limit : term += [fs.pop(0)] ret += [term] if not ret : ret = [[1]] if not as_string : return [reduce(lambda a,b:a*b, q) for q in reversed(ret)] else : pp = "x".join([str(reduce(lambda a,b:a*b, q)) for q in reversed(ret)]) return pp if len(ret) == 1 else "("+pp+")"First few results: