# Parabolas appearing in y = a mod floor(x)

I was just observing the simple function

$$y=a \text{ mod }\text{floor}(x)$$

and for large $$a$$, some shapes which look like parabolas started appearing. Here, for example, is $$a=1,500,000$$:

What is the intuition for this? There must be something special about the values of $$x$$ where they appear.

You can play with the function here. Press the play button on $$a$$ to watch the parabolas form as $$a$$ increases. https://www.desmos.com/calculator/etgmlsjekm

Nice question! The floor function isn't particularly relevant since we can just restrict our attention to integer values of $$x$$, or equivalently think of this as just a function of $$n = \lfloor x \rfloor$$. I will only talk about $$n$$ from now on. We can write

$$a \bmod n = a - n \left\lfloor \frac{a}{n} \right\rfloor$$

to get a sense for how this value changes as $$n$$ changes. If $$n$$ increments to $$n+1$$ then the $$n$$ above increments by $$1$$ but then the term $$\left\lfloor \frac{a}{n} \right\rfloor$$ gets smaller. How much smaller depends on how large $$a$$ is relative to $$n$$. Specifically, we have that

$$\frac{a}{n} - \frac{a}{n+1} = \frac{a}{n(n+1)}$$

from which we see that if $$a$$ is small compared to $$n(n+1)$$ then $$\frac{a}{n}$$ only changes by a small enough amount as $$n$$ increases that $$\left\lfloor \frac{a}{n} \right\rfloor$$ will spend a lot of time constant; more specifically if $$a$$ is small compared to $$n(n+1) \approx n^2$$. This is where the lines come from in the plot for small values of $$a$$, such as this plot for $$a = 50000$$:

We expect lines to start appearing when $$\frac{a}{n(n+1)}$$ is small compared to $$1$$; say we want $$\frac{a}{n(n+1)} \approx \frac{1}{10}$$, which gives $$n \approx \sqrt{10a}$$, which here gives $$n \approx 700$$ and this is roughly what we see in the plot.

What happens when $$a$$ is about the same size as $$n(n+1)$$? In that case $$\left\lfloor \frac{a}{n} \right\rfloor$$ starts decreasing by $$1$$ as we increment $$n$$; in other words it becomes linear, so when multiplied by $$n$$ the result becomes quadratic. You can see this clearly in the plot for $$a = 10^6$$ where there's a clear single parabola around $$n = 10^3$$:

But the other parabolas are stacked on top of each other; what's going on with that? Well, you can see that there's a double parabola a bit under $$n = 1400$$; with all these square roots running around you might guess that it is actually occurring close to $$n = 1414$$, the first few digits of $$\sqrt{2}$$; this corresponds to when $$\frac{a}{n(n+1)}$$ is close to $$\frac{1}{2}$$, meaning that $$\left\lfloor \frac{a}{n} \right\rfloor$$ will (most of the time, hopefully) alternate between being constant and increasing by $$1$$ as we increase $$n$$; this corresponds to the two stacked parabolas.

The three stacked parabolas around $$n = 1700$$ correspond to $$\frac{a}{n(n+1)}$$ being close to $$\frac{1}{3}$$, since $$\sqrt{3} = 1.732 \dots$$. More generally we expect to see $$q$$ stacked parabolas when $$\frac{a}{n(n+1)}$$ is close to the fraction $$\frac{p}{q}$$ in lowest terms; you can see that this is consistent with the four stacked parabolas around $$n = 2000$$ which corresponds to $$\frac{a}{n(n+1)}$$ being close to $$\frac{1}{4}$$, as well as the more faint three stacked parabolas around $$n = 1200$$ which corresponds to $$\frac{a}{n(n+1)}$$ being close to $$\frac{2}{3}$$ (we have $$\sqrt{\frac{3}{2}} = 1.224 \dots$$).

Expressing this relationship in terms of $$n$$, we expect to see $$q$$ stacked parabolas around $$n \approx \sqrt{\frac{aq}{p}}$$ where $$0 < \frac{p}{q} < 1$$ is a fraction in lowest terms, at least for $$q$$ reasonably small; in the plot above we can clearly distinguish a $$q = 9$$ stack, for example, around $$n = 3000$$. The parabolas become noticeably fainter for $$p > 1$$ but you can still see a few of them.

• The plot for $a = 1.5 \times 10^6$ is a little misleading because it's a little hard to tell where the parabolas are except for the ones at $n = 1500$ and $n = 3000$ and that makes you think about divisors of $a$ which is not quite what's going on. The more important clue is that $a$ is roughly twice the order of magnitude of the values of $n$ being plotted. Sep 8, 2022 at 4:02