Multiplying to make sorted sequence - limit on multiplicand

Question

Given a list of positive integers $ x_1, x_2, x_3, \ldots, x_n $, we can find positive integer coefficients $ c_1, c_2, c_3, \ldots, c_n $ such that

$$ c_1x_1 \lt c_2x_2 \lt c_3x_3 \lt \ldots \lt c_nx_n $$

(For eg., for $ 5, 4, 12, 1, 3 $, the coefficients $ 1, 2, 1, 13, 5 $ produce the increasing list $ 5, 8, 12, 13, 15 $.)

There is a smallest (i.e. least in value) set* of such coefficients for a given list. What is an upper bound, in terms of values in the given list, on the largest coefficient in such a minimum-value set of coefficients?

* By smallest, what I have in mind is the result of this iterative process:
$ c_1 = 1 $.
$ c_2 $ is the smallest positive integer such that $ c_2 x_2 \gt x_1 $.
$ c_3 $ is the smallest positive integer such that $ c_3 x_3 \gt c_2 x_2 $.
$ c_4 $ is the smallest positive integer such that $ c_4 x_4 \gt c_3 x_3 $.
And so on.
I think this might be the same as saying the set of coefficients with the least sum, but in case it is not, the above is the actual expected answer.

Answer 1

With your "algorithm", you have, for all $k$, by choosing the least possible $c_{k+1}$ ($\lfloor x\rfloor$ being the greatest integer lower than $x$): $$c_{k+1}=\left\lfloor\frac{c_kx_k}{x_{k+1}}\right\rfloor+1\le \frac{c_kx_k}{x_{k+1}}+1$$ So for example : $$c_2\le \frac{c_1x_1}{x_2}+1 = \frac{x_1+x_2}{x_2}$$ $$c_3\le \frac{c_2x_2}{x_3}+1=\frac{x_1+x_2+x_3}{x_3}$$ And so on. More generally : $$(\forall k)\ c_k\le \frac{x_1+x_2+\dots+x_k}{x_k}$$ So one simple majoration for your coefficients is : $$(\forall k)\ c_k\le \sum_{i=1}^n x_i$$ Is that the kind of majoration you are looking for ?

Answer 2

If any of the $x_i$ are large enough that we can get away with $c_i=1$ it essentially breaks the sequence. We can ignore all the $x$'s before and start the sequence there. If we start with some number for $x_1$ we can imagine choosing the rest of the $x$s to make the products as large as possible while not having any $c_i$ except the last be $1$. We want $x_2=x_1-1$, which gives $c_2=2$ and the second product is $2(x_1-1)$. The pattern continues with $x_3=2(x_1-1)-1, c_3=2,$ product $4x_1-6$. Then $x_4=4x_1-7,$ product $8x_1-14$. We get that the $k^{th}$ product is $2^{k-1}x_1-2^{k+1}+2$. Finally we choose $x_n=1$, which forces $c_n=2^{n-2}x_1-2^n+3$. I think that is as large as you can force for the given $x_1$. All the $c$s except the first and last are $2$. Starting with $x_1=10$ and letting $n=8$ we get the following $$\begin {array} {r r r r}i&x_i&c_i&x_ic_i\\ \hline1&10&1&10\\ 2&9&2&18\\3&17&2&34\\4&33&2&66\\5&65&2&130\\6&129&2&258\\7&257&2&514\\8&1&515&515 \end {array}$$