CODEWITHSUNDEEP
algorithmprimesmathematical-optimization
Daniel
Daniel

Reputation: 944

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?

Upvotes: 1

Views: 449

Answers (2)

user1952500
user1952500

Reputation: 6771

By the AM-GM inequality and using the other constraints you can get:

(n / k)^k > product >= n^d

Hence n^(k-d) > k^k. Taking log to base n we get: k-d > k*log(k). Since k <= n ( based on the sum) k * (1 - log(k)) > d

You can plot the LHS above to get an estimate of k.

Upvotes: 0

Brett Hale
Brett Hale

Reputation: 22328

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.

Upvotes: 1

Related Questions