Finding the nonnegative integer exponents that minimize a product

Question

I've been trying to solve a problem which seems to be a multiplicative optimization problem:

Given a threshold $T > 0$, and a set of integers $b_1, b_2,\dots, b_n > 0$, find integer exponents $e_1, e_2, \dots, e_n \geq 0$ such that

$$P := \prod b_i^{e_i}$$

is the smallest integer in that form and greater than or equal to $T$.

Another possible optimization criterion is to relax on $P$ but find exponents such that $\sum e_i$ is minimized.

I'd really appreciate some pointers (not necessarily solutions) to help me get started.

Thank you in advance!

Answer 1

Note that $$ \ln P=\ln(\prod_{i}b_i^{e_i})=\sum_i\ln{b_i^{e_i}}=\sum_ie_i\ln b_i $$ In other words, $\ln P$ is linear with respect to variables $e_i$, which is good news.

Your problem is thus equivalent to $$ \min\limits_{e_i\in \mathbb{N}}\;\left\{\sum_{i=1}^n (\ln b_i) e_i\;|\; \sum_{i=1}^n(\ln b_i) e_i\ge \ln{\tau},\; \prod_{i=1}^n b_i^{e_i} \in \mathbb{N}\right\} $$

As pointed out by Rodrigo de Azevedo, you can omit the last constraint ($\prod_{i=1}^n b_i^{e_i} \in \mathbb{N}$) if $b_i$ and $e_i$ are positive integers. Therefore, in this case, your problem is a pure integer linear problem, easy to solve.

So you end up with $$ \min\limits_{e_i\in \mathbb{N}}\;\left\{\sum_{i=1}^n (\ln b_i) e_i\;|\; \sum_{i=1}^n(\ln b_i) e_i\ge \ln{\tau}\right\} $$

You can solve this with dynamic programming if $\tau$ is also integer:

Let $$ f_j(t)=\min\limits_{e_i\in \mathbb{N}}\;\left\{\sum_{i=1}^j(\ln b_i) e_i\;|\; \sum_{i=1}^j(\ln b_i) e_i\ge \ln{t}\right\} $$ Now, either you set $e_{j+1}$ to $0$, and you have $f_{j+1}(t)=f_j(t)$, either you set $e_{j+1}$ to $\lambda\in \left\{ 1,\cdots, \left\lceil \frac{\ln t}{\ln b_{j+1}} \right \rceil \right\} \subset \mathbb{N} $, and $f_{j+1}(t)$ equals $\lambda \ln b_{j+1}$, plus the optimal solution for the remaining $j$ variables, with a threshold set to $\ln t-\lambda\ln b_{j+1}=\ln\frac{t}{b_{j+1}^{\lambda}}$. Therefore, the following recursive equations hold: $$ f_{j+1}(t)=\min\limits_{\lambda\in\left\{ 1,\cdots, \left\lceil \frac{\ln t}{\ln b_{j+1}} \right \rceil \right\}} \left\{ \lambda \ln b_{j+1}+f_j\left(\frac{t}{b_{j+1}^{\lambda}}\right)\right\} $$ with $$ f_1(t)= \begin{cases} 1 \quad\; \mbox{if}\quad b_1 \ge t\\ \infty \quad \mbox{if} \quad b_1 < t \end{cases} $$

Compute $f_n(\tau)$ with this recursion and you are done (it will take $\mathcal{O}(n\ln^2\tau)$ operations).

---

K.G. proposed a quick non-DP implementation to illustrate the idea.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
#include <cmath>
#include <limits>

using namespace std;

vector<int> base_vec = {2, 3, 4, 5, 6, 8};
const int base_size = base_vec.size();

pair<vector<int>, int> good_size_recursive (int idx, int t)
{
    pair<vector<int>, int> res;
    res.first = vector<int>(base_size);
    vector<int> ret_exp = vector<int>(base_size);

    if (0 == idx) 
    {
        int lambda = static_cast<int>(ceil(log(t)/log(base_vec[0])));
        ret_exp[0] = lambda;
        int best_bound = static_cast<int>(pow(base_vec[0], lambda));
        res = make_pair(ret_exp, best_bound);
        return res;
    }

    int best_bound = numeric_limits<int>::max();
    //fixed error in lambda calculation
    int lambda = static_cast<int>(ceil(log(t)/log(base_vec[idx])));

    for (int i = 0; i <= lambda; i++)
    {
        pair<vector<int>, int> curr_res;
        curr_res = good_size_recursive(idx - 1, 
            static_cast<int>(ceil(
                (double)t/pow(base_vec[idx], i)
                ))
            );
        int curr_bound = curr_res.second * static_cast<int>(pow(base_vec[idx], i));

        if ((curr_bound < best_bound) && (curr_bound >= t))
        {
            best_bound = curr_bound;
            res = curr_res;
            res.first[idx] = i;
            res.second = curr_res.second * static_cast<int>(pow(base_vec[idx], i));
        }
    }

    return res;
}

int main () {
    int t;
    cout << "Please enter t: ";
    cin >> t;

    pair<vector<int>, int> sol = good_size_recursive(base_size - 1, t);
    cout << "base sizes:" << endl;
    for (auto b : base_vec)
        cout << b << '\t';
    cout << endl << "exponets:" << endl;
    for (auto s : sol.first)
        cout << s << '\t';
    cout << endl << "Result:" << endl;    
    cout << sol.second << endl;

    return 0;
}