Algorithm for finding sequence verifying a floor equation

Question

We are looking for an algorithm solving the following problem.

Given a sequence $ 0 < x_1< \dots < x_n $ find a sequence $0 < y_1 < \dots < y_n$ such that $\forall j \in \{2, \dots, n-1\}, i \in \{1, \dots, j-1\}, y \in [y_j, y_{j+1}[ \quad \left\lfloor \frac{y}{y_i} \right\rfloor= \left\lfloor \frac{y_{j+1}}{y_i} \right\rfloor ,$

while minimizing $\sum_{i=1}^n a_i |y_i - x_i| $ with $a_1,\dots,a_n \in \mathbb{R}^+$.

The distance may be replaced by another of the same spirit if it allows for a nice solution.

Answer 1

Here is a solution, likely sub-optimal.

$ \forall i \in \{1, \dots, n-2\}, \; \text{let} \; f_i: x \mapsto (\left\lfloor {x}/{x_i} \right\rfloor + 1) \; x_i$.

1. Set $ y_1 := x_1 $ and $ y_2 := x_2 $.
2. $ \forall k \in \{3, \dots, n\} $ set $ y_k := \min \left[ x_k, \min_i f_i(x_k) \right]. $

Another solution is to correct $ x_2 $:

1. Set $ y_1 := x_1 $.
2. Set $ y_2 := \max (x_2, (\left\lfloor x_3/x_1 \right\rfloor) \; x_1 )$
3. $ \forall k \in \{4, \dots, n\} $ set $ y_k := \min \left[ x_k, \min_i f_i(x_k) \right]. $