Search code examples
algorithmprimesmathematical-optimization

minimizing the sum with a lower bound on the product

I have an optimization problem that I'm currently solving by brute force, but I'm hoping there is a better way.

Problem: Given n and d, find prime powers p1^e1, ..., pk^ek (pis are distinct) such that

  1. p1^e1 * ... * pk^ek >= n^d
  2. p1^e1 + ... + pk^ek < n is minimal

My current solution is to iterate through all possible subsets of primes (up to some fixed number), then iterate through all possible exponents (up to some fixed number), then test condition 1, then see if the sum is the smallest so far. This takes a really long time. Is there something more clever that I can do to speed this up?

Solution

  • This seems like a knapsack problem. I suspect it is NP-complete. In fact, if (d = 1), an optimization might be equivalent to factoring.

    Not all Knapsack problems are NP-hard however - which is why the Merkle–Hellman knapsack cryptosystem was broken.