Consider the following algorithmic task:
Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\prod_i p_i^{d_i}$, subject to the requirements that $0 \le d_i \le e_i$ and $\prod_i p_i^{d_i} \le M$.
What is the complexity of this problem? Is it NP-hard?
This problem is equivalent to the following:
Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\sum_i d_i \log p_i$, subject to $0 \le d_i \le e_i$ and $\sum_i d_i \log p_i \le \log M$.
This can be seen to be an instance of bounded knapsack with $k$ items, where the $i$th item has weight $\log p_i$ and value $\log p_i$ and can be used at most $e_i$ times, and where the capacity of the knapsack is $\log M$. (See the footnote below for a more careful statement.) Thus, my problem is a special case of bounded knapsack. It follows that my problem is in NP.
But is my problem NP-hard?
For instance, is there a way to reduce from bounded knapsack to my problem? It's not clear, because my problem limits the weights and values to be something specific related to the log of primes, rather than arbitrary values.
Footnote: strictly speaking, the bounded knapsack requires item weights and values to be integers, whereas $\log p_i$ isn't an integer. However, we can fix this up by picking a sufficiently large constant $K$ and using $\lfloor K \log p_i \rfloor$ as the weight and value of the $i$th item, and use $\lfloor K \log M \rfloor$ as the capacity of the knapsack. With this fix-up, my problem now becomes a special case of bounded knapsack, or reduces to bounded knapsack.
