# 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

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8976393342018127, "perplexity_flag": "middle"}