I encountered this problem while I was programming and trying to write an algorithm for a data structure and thought that maybe there was a dynamic programming approach that could solve this. I am not entirely sure if this is more of a math problem or a computer science one.
Problem: Assume that we have a positive integer $z$ and a list of primes in ascending order:
$$p_1 \leq p_2 \leq \cdots \leq p_i \leq p_{i+1} \leq \cdots \leq p_n$$ (where primes can repeat). The primes satisfy the following properties:
a) no $p_j$ is greater than $z$
b) $p_1 p_2 \cdots p_n > z$
The goal is to find an algorithm that finds a sublist $p_{a_1}, \ldots, p_{a_k}$ of primes from the list $p_1, \ldots, p_n$ that satisfies two conditions:
$p_{a_1}p_{a_2} \cdots p_{a_k} > z$
the product $p_{a_1} p_{a_2} \cdots p_{a_k}$ is the minimal possible of all sublists that satisfy condition 1.
[In other words, we want to find a sublist whose product is greater than $z$ and also require that the sublist's product is as close to $z$ as possible]
My main question is whether there is an algorithm that is efficient(polynomial time?). The brute force solution I found was to write down a list of all possible sublists with product greater than $z$ and this list will be finite and then just take the minimum element, but this algorithm would be O($2^n$) since enumerating all possible sublists would give $2^n$ possibilities since you either include or exclude a $p_i$.
A note on why I made the three assumptions above:
a)- this is an assumption because such a $p_j$ could never be used in a minimal list that satisfies condition 2, so we just ignore them if they were in our list.
b)- this is an an assumption because I need this condition in my code.