6
$\begingroup$

I am not a mathematician, and corrections are welcome (including tags).

Background:

For the last few days, i have been interested in the problem of placing points along a line segment (of length $1$, for simplicity), such that no matter how many points are added, the points are still relatively evenly spaced.

This is somewhat vague, so let's look at one specific sequence based on the golden ratio, which seems to fit the description:

$p_n = \left\{n\phi\right\}$

By $\{\cdot\}$, I mean the fractional part function. Here is one example of how this sequence is interesting (middle column).

The question:

Given the sequence defined above of length $s$ and a freely chosen point $x$ between $0$ and $1$, how can I find the point $p_n$ closest to $x$, where $n \leq s$?

  • 0
    @Jostein: I think you are right about avoiding clumping, and this comes from $\phi$ being "most irrational".2011-07-14

1 Answers 1

3

Take the largest Fibonacci number $F_m\le s$. Find the nearest fraction $k/F_m$ to $x$. Consider the numbers $n_p=[(-1)^m F_{m-1}(k+p)]\mod F_m$ and n'_p=F_m+n_p (if the latter is in the admissible range) with integer $p\in[-4,4]$ (this should be enough and I'm too lazy to check if we can do $[-3,3]$ or even $[-2,2]$). Now just compare the results for these 18 values and choose the best one. The reason is that $\varphi-\frac{F_{m+1}}{F_m}$ is so small that $n\varphi-n\frac{F{m+1}}{F_m}$ is not much bigger than $1/F_m$ for all $n\le s$.