Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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