# Finding the closest match in a “golden” sequence of points

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

-
Interestingly, i see that the fibonacci numbers give values of n for which $p_n$ approaches 0. – Jostein Jul 14 '11 at 10:29
I think some of the lack of clarity stems from mixing of uppercase and lowercase (I assume $P_n$ and $p_n$ are supposed to refer to the same thing?) and unorthodox use of the term "distribution" (which usually means a probability distribution, whereas you seem to mean more something like a set or a sequence). In the first case, one would speak of its "size", in the second of its "length". If this is correct, then editing the question accordingly would go a long way towards clarifying it. – joriki Jul 14 '11 at 10:45
The sequence $F_n\phi \mod 1$ tends to zero/one because the ratios $F_n/F_{n-1}$ are the partial continued fractions (called "convergents") of $\phi$. See the following bound from Wikipedia: en.wikipedia.org/wiki/… – anon Jul 14 '11 at 10:45
Also, "$s>n$" doesn't really make sense as it stands, since $n$ is yet to be found -- I assume you mean "a distribution of size $s$" and then you want to find the point $p_n$, with $n\le s$, which is closest to $x$? – joriki Jul 14 '11 at 10:47
I have tried to clarify the question based on joriki's helpful feedback. – Jostein Jul 14 '11 at 11:12

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