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
    Couldn't $f(2)$ be as well 75 instead of 25? It seems, your function i not well-defined. Also, what is your question?2011-02-18
  • 0
    Yes, f(2) could be 75 instead of 25.. I forget to mention, sorry. The point is I need a function where any f(n) has the maximum distance to any other f(x) where 0<=x<=n2011-02-18
  • 0
    More: the problem is the same as to generate the sequence: {0,1/2,1/4,2/3,1/8,3/8,5/8,7/8,1/16,3/16... } and the multiply the i-th value by n.2011-02-18
  • 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$.