26
$\begingroup$

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

enter image description here

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

$\endgroup$

1 Answer 1

24
$\begingroup$

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

enter image description here

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

enter image description here

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.

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Sep 8, 2022 at 4:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .