Gradual monotonic morphing between two natural numbers

Question

Let $a < b$ be two natural numbers. I will use these as an example: \begin{align*} a & = 2^5 \cdot 3^2 \cdot 5^2 = 7200\\\ b & = 2^3 \cdot 3^5 \cdot 7^1 = 13608 \end{align*} I seek to "morph" $a$ to $b$ via $a{=}n_0,n_1,n_2,\ldots,n_k{=}b$ such that

• Each step is upward: $n_{i-1} < n_i < n_{i+1}$ (monotonic).
• $\textrm{gcd}(a,b) \mid n_i$. (So the core common factors are retained.)
• $n_i \mid \textrm{lcm}(a,b)$. (So no other prime factors may be introduced.)
• $k$ is maximized, i.e., the number of steps is maximized. (This is the sense of "gradual.")

So in the case of the example, we need to multiply $a$ by $2^{-2} \cdot 3^3 \cdot 5^{-2} \cdot 7^1 = 189/100$ to reach $b$, in discrete, increasing steps. We can always achieve this in a single $k{=}1$ upward step.

Try 1: Starting with $2^{-1} \cdot 3^1=3/2$, and repeating $2^{-1} \cdot 3^1$, seems promising, but that leaves $3^1 \cdot 5^{-2} \cdot 7^1 = 21/15 < 1$, and so the 3rd step is downward.

Try 2: Another try is to start with $5^{-1} \cdot 7^1=7/5$, and then $3^2 \cdot 5^{-1}=9/5$, but then what remains is $2^{-2} \cdot 3^1 = 3/4 < 1$, again a downward move.

Try 3,4: It appears there are two $2$-step solutions: \begin{align*} 2^{-1} \cdot 3^1 = 3/2 > 1 &\;\textrm{followed by}\; 2^{-1} \cdot 3^2 \cdot 5^{-2} \cdot 7^1 = 63/50 > 1\\\ 2^{-2} \cdot 7^1 = 7/4 > 1 &\;\textrm{followed by}\; 3^3 \cdot 5^{-2} = 27/25 > 1 \end{align*} The corresponding "morphs" are \begin{align*} 7200 \to & 10800 \to 13608\\\ 2^5 \cdot 3^2 \cdot 5^2 \to & 2^4 \cdot 3^3 \cdot 5^2 \to 2^3 \cdot 3^5 \cdot 7^1\\\ 7200 \to & 12600 \to 13608\\\ 2^5 \cdot 3^2 \cdot 5^2 \to & 2^3 \cdot 3^2 \cdot 5^2 \cdot 7^1 \to 2^3 \cdot 3^5 \cdot 7^1 \end{align*}

Q.Given factorizations of $a$ & $b$, can an optimal (maximum number of intermediate $n_i$'s) morph be directly calculated from the factorizations, or must one resort to a combinatorial optimization?

There is a sense in which I seek a particular path in a graph, but I am not seeing that clearly...

Answer 1

If I understand the question right, then $k$ is simply the number of divisors $d$ of $\text{lcm}(a,b)$ such that $a\le d\le b$ and $d\mid\gcd(a,b)$. (So in finding a longest chain, we may assume that $a$ and $b$ are relatively prime.)

In your example, a longest chain would be \begin{equation} 7200\to 7560\to 7776\to 9072\to 9720\to 10080\to 10800\to 12600\to 12960\to 13608 \end{equation} I doubt that the length can be determined without some sort of actually computing the divisors. One can interpret these divisors (via their exponents) as lattice points in a polytope: Suppose that $a$ and $b$ are relatively prime, and $p_1,p_2,\dots,p_r$ are the primes dividing $ab$. Then $k$ is the number of integral $e_i$ such that \begin{equation} \log a\le\sum_{i=1}^re_i\log p_i\le\log b. \end{equation} Taking the volume of the polytope as an approximation of the number of the lattice points in this polytope, we see that $k$ is about (in a vague sense of course) \begin{equation} \frac{1}{r!\prod\log p_i}((\log b)^r-(\log a)^r). \end{equation}