2
$\begingroup$

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...

$\endgroup$
5
  • $\begingroup$ Why isn't a three element chain including both 10800 and 12600 allowed? Gerhard "Climbing A Partial Divisibility Lattice?" Paseman, 2015.11.22 $\endgroup$ Nov 23, 2015 at 2:19
  • $\begingroup$ sorry, step instead of element. Gerhard "Was Distracted From Comment Editing" Paseman, 2015.11.22 $\endgroup$ Nov 23, 2015 at 2:26
  • 1
    $\begingroup$ I think your problem is equivalent to listing all divisors of a number that lie in a certain interval. Gerhard "Or Else I'm Missing Something" Paseman, 2015.11.22 $\endgroup$ Nov 23, 2015 at 2:31
  • 1
    $\begingroup$ Dividing your example by 72, I start at 100 and go up to 105 , 108, 126, 135, and then their reciprocals w.r.t 18900. Is this what you had in mind? Gerhard "Gradually Understanding The Problem Characteristics" Paseman, 2015.11.22 $\endgroup$ Nov 23, 2015 at 3:58
  • $\begingroup$ @GerhardPaseman: You are right, as Peter Mueller's answer shows in detail. $\endgroup$ Nov 23, 2015 at 14:00

1 Answer 1

2
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.