Shortest-depth routing algorithm

Question

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!

Answer 1

Problem statement

Define the function $f$ by

$$f(a_1,\dots,a_k) = \sum_{i=0}^k \prod_{j=1}^i a_i.$$

In other words,

$$f(a_1,\dots,a_k) = 1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k.$$

Given $n$, you are looking for $a_1,\dots,a_k$ that form a solution to the equation

$$f(a_1,\dots,a_k) = n.$$

A useful lemma

Let me point out a useful property of the function $f$:

$$f(a_1,a_2,\dots,a_k) = 1 + a_1 f(a_2,\dots,a_k).$$

This follows immediately from the identity

$$1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k = 1 + a_1 (1 + a_2 + a_2 a_3 + \dots + a_2 \cdots a_k).$$

An algorithm for your problem

Now we get a reasonable algorithm for your problem, using dynamic programming.

Each subproblem is indexed by $(i,n')$, and records the best sequence $a_i,a_{i+1},\dots,a_k$ such that $f(a_i,a_{i+1},\dots,a_k)=n'$. Now we can find the best solution to the original problem by enumerating all possible values for $a_1$, then looking for a solution to the $(2,(n-1)/a_1)$-subproblem. And, we can solve the $(i,n')$-subproblem by enumerating possible values of $a_i$ and looking for a solution to the $(i+1,(n'-1)/a_i)$-subproblem. Of course, as a straightforward optimization, we can limit our search to only values of $a_i$ that are a divisor of $n'-1$.

How many subproblems are there, in all? A simple bound is that there are at most $kn$ subproblems, so the running time of this algorithm is at most $O(kn^2)$. Using the optimization, I expect the running time will be much less in practice, as most values of $n'$ have only a limited number of divisors. (See also this question for a math question that is related to the efficiency of this dynamic programming algorithm.)

Another optimization

Here is one more optimization you could apply. You could use modular arithmetic to quickly filter out subproblems that have no solution.

Suppose we have a small prime $p$, and we have fixed values of $k,n$. Then if there exists a solution to $f(a_1,\dots,a_k) = n$, then there exists a solution $f(a_1,\dots,a_k) \equiv n \pmod p$; conversely, if there is no solution to $f(a_1,\dots,a_k) \equiv n \pmod p$, then there is no solution to $f(a_1,\dots,a_k) = n$.

So, we could pick a small prime $p$, and then tabulate for which values of $(i,n')$ the $(i,n')$-subproblem has a solution. Note that we only care about the value of $n'$ modulo $p$, so there are only $kp$ such subproblems, and we can enumerate which ones have a solution in $O(kp^2)$ time using dynamic programming. (We cannot use the divisibility optimization any longer.)

So, we could precompute a table of size $kp$ and use it to filter out subproblems. Before trying to solve the $(i,n')$-subproblem, we first look up $(i,n' \bmod p)$ in our table to see whether it has a solution modulo $p$. If it doesn't have a solution modulo $p$, we don't try to explore that subproblem (we don't try to look for a solution in the integers; we know it'll fail).

We can build a table for each of a handful of small primes, say $p=2,3,5,\dots,17$, and check against each of these tables before exploring a subproblem. This might reduce the number of subproblems that have to be explored, and thus improve efficiency.

Can we use this idea plus the Chinese remainder theorem to solve the original problem? Unfortunately not: the requirement that $a_i \le m$ does not behave well under modulo arithmetic. Thus, if all we wanted to know is whether there exists some sequence of positive integers $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$, then we could solve that in $\text{poly} \log (n)$ time by looking for a solution modulo a set of small primes whose product exceeds $n^k$, then applying the Chinese remainder theorem. However, your question asks whether there exists a sequence $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$ such that $a_i \le m$ for each $i$, and that cannot be solved efficiently in such a way. If you were willing to drop the requirement that $a_i \le m$, then your problem could be solved a lot more efficiently.