MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The sequence n mod i

Consider the sequence n mod i for i=1...$\sqrt{n}$. If we draw the sequence as an xy-plot, we get a dense triangle (since n mod i < i). More precisely, the limiting density of the figure is uniform across the allowable triangle (I think you can prove this using Weyl's equidistribution criterion).

Local minima of the sequence

Now suppose we take only local minima of the sequence. If we do this, we get what look like dense triangles (beware: slowly loading!), with some outliers between the triangles. One explanation goes like this: $n \mod i = i \cdot frac(n/i)$; if i is increased or decreased by 1, the change will be roughly $i \cdot frac(n/i^2)$; so a local minimum must always lie below $i \cdot sfrac(n/i^2)$ (sfrac is the distance to the closest integer). This accounts for the 'triangles' (enumerate over the integer closest to $n/i^2$ and its direction). Outliers are explained by our approximation being especially bad when $sfrac(n/i^2)$ is small.

What is the limiting density (if any) of this sequence? How many outliers are there, asymptotically?

In order to make the question of density meaningful, we need to normalize the axes through division by $\sqrt{n}$. The weight of each point should be $1/\sqrt{n}$.

Further iterations

The process of taking local minima can be iterated. Local maxima can also be mixed. Using reasoning similar to the above, one can come up with equations for the limiting curves, which conform with experimental data. The equations can be found in the pdf linked to above.

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.