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
    Interestingly, i see that the fibonacci numbers give values of n for which $p_n$ approaches 0.2011-07-14
  • 1
    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.2011-07-14
  • 0
    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: http://en.wikipedia.org/wiki/Continued_fraction#A_property_of_the_golden_ratio_.CF.862011-07-14
  • 1
    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$?2011-07-14
  • 0
    I have tried to clarify the question based on joriki's helpful feedback.2011-07-14
  • 0
    In what you are doing there is nothing special about $\phi$. You could use any irrational with the same result.2011-07-14
  • 0
    @ross That is a good point. However, some irrationals are "less effective", in that they need a longer seqence before the the points acheive somewhat even spacing. At least for some irrationals. I belive the golden ratio is optimal in this sense, but i could be mistaken.2011-07-14
  • 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$.