More clearly stated than title, let $n \in \mathbb{N}$ and $A = \{m \in \mathbb{N} : m \geq n \text{ and } m = 2^a 3^b 5^c 7^d \text{ for some } a,b,c,d \in \mathbb{N}\}$. Find $\min(A)$. This can be brute force calculated in $\prod_{k=2,3,5,7} \log_k(n)$ calculations in a "quadruply nested" for loop, since you know that the values for $a, b, c, d$ can never exceed $\log_2(n), \log_3(n), \log_5(n), \log_7(n)$ respectively. Can this complexity be improved or is it optimal? The context of this is for optimization of memory allocations for FFT.
A thought that does not work follows. Compute the prime factorization of $n$ and split as $n = 2^w 3^x 5^y 7^z \cdot q$ where $q$ is the "rest" of the factorization with larger primes. Then somehow take the factorization of $q$ to recursively solve the same problem and use those results. However, this does not seem to work for $n = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13$. The correct answer is $150$ for the $q$ part of $11 \cdot 13 = 143$. My idea doesn't work because the answer to the same problem of "find $\min(A)$" for the case $n = 11$ is $m = 12$ and similary for $n=13$ is $14$. Then $12\cdot 14 = 168 > 150$ and so this doesn't work. Basically then $11 \cdot 13$ would have to be its own base case in recursion, and my guess is that you'd never get a true base case and that this approach just straight up does not work.
You can do that in (log n)^2 log log n operations.
Find all products $2^a \cdot 7^d$ up to and including the first one that is ≥ n, and sort them in ascending order to form a sequence $x_i$.
Find all products $3^b \cdot 5^c$ up to and including the first one that is ≥ n, and sort them in descending order to form a sequence $y_i$.
The product you are looking for is some $x_i$, multiplied by the last $y_j$ that makes the product ≥ n. You start with j = 1 and i = 1 and check $x_i y_j$. As long as that product is ≥ n then it might be the smallest product ≥ m, and you increase j. Then as long as the product is < n you increase i by 1 until you have another product ≥ n. You finish when all numbers are processed.
Most operations are performed (log n)^2 times, except the sorting adds a factor log log n. You don't need to store (log n)^2 numbers if you generate the lists $x_i$ and $y_j$ on the fly.
Similar schemes can be used often to handle 2k lists using k loops.