This problem came up in a graph network routing context, it can be expressed as follows:
Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k \rangle$ such that:
$$1 + \sum_{i = 1}^k \prod_{j = 1}^i a_j = n$$
With the added condition that $a_i \leq m$ for all $1 \leq i \leq k$.
(for a challenge, add the constraint "with the least number of $1$'s", but the above would suffice)
Graphically, if you picture a tree of depth $k$ (with a single root) with branching factors $a_i$ at each level, the algorithm asks for the shortest such tree containing exactly $n$ nodes in it, with each branching factor at most $m$. For instance, taking $n = 12$ and $m = 5$ as an example, we see that $\langle 1, 1, 3, 2 \rangle$ is a solution, since:
$$1 + (1) + (1 \cdot 1) + (1 \cdot 1 \cdot 3) + (1 \cdot 1 \cdot 3 \cdot 2) = 1 + 1 + 1 + 3 + 6 = 12$$
Which corresponds to the tree with branching factors $1, 1, 3, 2$ shown below:
But there is a shorter solution, given by $\langle 1, 2, 4 \rangle$, as illustrated by the tree:
And there is no shorter solution with $m = 5$, in fact the only other solution of length $3$ is $\langle 1, 5, 1 \rangle$. Note the solutions need not start with $1$, e.g. $\langle 4, 3, 1 \rangle$ for $n = 29$ (the order is clearly very important).
We are talking $n \approx 10^8$, $m \approx 10^4$ in my case (but asymptotic algorithms are welcome!)
I solved it quickly using a brute force approach, which is pretty inefficient, running in exponential time. Is there an easy lower/upper bound on the length of the smallest solution in terms of both $n$ and $m$, and an efficient algorithm to find one such solution? My first thought was a backtracking algorithm, but it doesn't seem to help since you usually get stuck at the leaves of the tree where you realize you can't find a branching factor that will make it add up to $n$, perhaps there is a clever number-theoretic algorithm to select good branching factors as you go?
One optimization I came up with is that if you are at depth $i$ in the tree, then you can calculate the number of nodes you've already added as $x$, then the branching factor for the next tree level must necessarily divide $n - x$, so it might be efficient to go for branching factors that lead to prime values of $n - x$, then we can build a set of optimal solutions for small primes and look them up as needed to complete the tree (going for primes with shorter solutions first). But that doesn't appear to guarantee a shortest solution...
Well, it does reduce the number of $a_i$ candidates to explore down to $O(\log(n))$, but in the absence of a better bound or a procedure to not have to explore fully the tree of possibilities for $a_{i + 1}, a_{i + 2}, \cdots$, this does not make for an efficient algorithm, even if the length of the shortest solution is (probably) upper-bounded by $O(\log(n))$.
Thanks!
PS: I wasn't totally sure what to tag this, so I filed it under combinatorics - please retag if there is a better category for this kind of problem!