1
$\begingroup$

Perhaps this is a very basic question, but I can't find a fast solution.

I have a cyclic interval [0,n] (distance from n to 0 is 1). I need a function that for a given value x returns the point in the interval where it maximizes the distance to all previous points (x-1, x-2...)

For instance, if n=100 and f(0) = 0

f(1) = 50 f(2) = 25 f(3) = 75 f(4) = 12'5 f(5) = 37'5 f(6) = 62'5 f(7) = 87'5 f(8) = 6'25 f(100) = ?? 

Note that f(0)=0 is for convinience, but you may start at f(0)=50.

At the end, what I need is that an uniform distribution for {f(0), f(1)... f(n)}

  • 0
    the sequence is {0,1/2,1/4,2/3,2/8,3/8,5/8,7/8,1/16,3/16... } Sorry2011-02-18

1 Answers 1

1

Suppose $f(0)=0$ and $n=1$. For positions $2^{a} \le i < 2^{a+1}$, the sequence takes on values of the form $k 2^{-(a+1)}$ for odd $k$ less than $2^{a+1}$. For a given $a$, these values can be covered in any order, since all the distances are equal; but concretely we may take $k=2(i-2^{a})+1$, so $ f(i; 0, 1) = \frac{2(i-2^{a})+1}{2^{a+1}} = \frac{i-2^{a}}{2^a} + \frac{1}{2^{a+1}} $ for all $i>0$, where $a = \lfloor\log_2(i)\rfloor$. More generally, for $f(0)=\alpha n$ and arbitrary $n$, we have $ f(i; \alpha, n) = \left(\frac{2\pi^{(a)}(i - 2^{a}) + 1}{2^a} + \frac{1}{2^{a+1}} + \alpha\right)n \mod n $ where each $\pi^{(a)}$ is an arbitrary permutation of $0,1,2,...,2^{a}-1$.