# Maximum distance in cycle interval

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)}

-
Couldn't $f(2)$ be as well 75 instead of 25? It seems, your function i not well-defined. Also, what is your question? –  Rasmus Feb 18 '11 at 10:30
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<=n –  Ivan Feb 18 '11 at 10:37
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. –  Ivan Feb 18 '11 at 11:05
the sequence is {0,1/2,1/4,2/3,2/8,3/8,5/8,7/8,1/16,3/16... } Sorry –  Ivan Feb 18 '11 at 11:23

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