1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What do you mean by "almost surely"? I don't see how the formal meaning would apply here. $\endgroup$ – Todor Markov Nov 22 '18 at 17:04
  • $\begingroup$ what is $n$, typically? $\endgroup$ – LinAlg Nov 25 '18 at 20:03
  • $\begingroup$ @LinAlg n is typically between 5 and 20 $\endgroup$ – Alfred M. Nov 26 '18 at 9:18
  • $\begingroup$ @TodorMarkov: True, this was ambiguous. I changed the formulation. $\endgroup$ – Alfred M. Nov 26 '18 at 9:19
  • $\begingroup$ 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)$ $\endgroup$ – LinAlg Nov 26 '18 at 13:48
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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