# Algorithm for finding sequence verifying a floor equation

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.

• What do you mean by "almost surely"? I don't see how the formal meaning would apply here. – Todor Markov Nov 22 '18 at 17:04
• what is $n$, typically? – LinAlg Nov 25 '18 at 20:03
• @LinAlg n is typically between 5 and 20 – Alfred M. Nov 26 '18 at 9:18
• @TodorMarkov: True, this was ambiguous. I changed the formulation. – Alfred M. Nov 26 '18 at 9:19
• Thank for you significantly modifying the question four days after a comment. The new formulation does not make much sense to me since you do not need the index $j$ as you require $\left\lfloor \frac{y}{y_i} \right\rfloor= \left\lfloor \frac{y_{i+1}}{y_i} \right\rfloor$ for all $i$ and for all $y$ in $[y_1,y_i)$ – LinAlg Nov 26 '18 at 13:48

$$\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].$$