# When does the first repetition in $\;\lfloor x\rfloor, \lfloor x/2 \rfloor, \lfloor x/3\rfloor, \lfloor x/4\rfloor, \dots\;$ appear?

Let $$\lfloor x\rfloor$$ denote the floor of $$x$$.

When does the first repetition in $$\lfloor x\rfloor$$, $$\lfloor x/2\rfloor$$, $$\lfloor x/3\rfloor$$, $$\lfloor x/4\rfloor$$, ... approximately appear, as a function of $$x$$?

It seems to be around ~ $$c \sqrt x$$.

Example: $$x = 2500$$:

2500, 1250, 833, 625, 500, 416, 357, 312, 277, 250, 227, 208, 192, 178, 166, 156, 147, 138, 131, 125, 119, 113, 108, 104, 100, 96, 92, 89, 86, 83, 80, 78, 75, 73, 71, 69, 67, 65, 64, 62, 60, 59, 58, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 43, 42, 41, 40, 40, 39, 39, 38, 37, 37, 36, 36, 35, 35, ...

• The first one happens between about $\sqrt{x}$ and $\sqrt{x}+\sqrt[4]{x}$ (for what's divided), or between $\sqrt{x}$ and $\sqrt{x}-\sqrt[4]{x}$ for the quotient. That $2500$ example is about as late as it can go. I might add details and make this a proper answer, but first I need sleep. – jmerry Jan 22 '19 at 14:33
• Thank you for your comment @jmerry. Yes, an answer (that might give another estimate than the current answer) would be welcome! – Basj Jan 22 '19 at 14:48
• @jmerry Please post your answer. Inspired by your claim I managed to prove roughly the same interval. I had the idea of how to get a narrower range than Lee Mosher, and was working on figuring out the proper length for "the short interval" when I saw your claim. If your method of proof is different from mine, so much better. If not, doesn't matter much. – Jyrki Lahtonen Jan 22 '19 at 18:02
• Exact solution obtained. – Yuri Negometyanov Jan 27 '19 at 16:51
• oeis.org/A257213 is worth a look – Barry Cipra Mar 10 '19 at 15:33

It's essentially the same as Jyrki Lahtonen's answer, but they invited me, so here's mine. Well, it's the same until the part where I go into detail about estimating where in that interval of potential values we actually get the first pair of equal values.

Let the sequence $$a_n$$, for $$n=1,2,\dots$$, be defined as $$\left\lfloor \frac xn\right\rfloor$$ for some positive real $$x$$. We seek the least $$n$$ for which $$a_n=a_{n+1}$$, or equivalently the greatest $$a$$ which appears twice in the sequence. Also, for convenience, define $$b_n=\frac xn$$. Note that the differences $$b_n-b_{n+1}=\frac{x}{n(n+1)}$$ form a decreasing sequence.

First, a fact about the floor and ceiling function: $$\lfloor u\rfloor + \lfloor v\rfloor\le \lfloor u+v\rfloor \le \lfloor u\rfloor + \lceil v\rceil$$, with equality when $$v$$ is an integer. What does this mean for our sequence $$a_n$$? When $$\frac xn - \frac x{n+1} \ge 1$$, $$a_n-a_{n+1}\ge 1$$ as well; we can't have two consecutive entries equal until $$b_n$$ has two consecutive entries that differ by less than $$1$$. From that, we will get our lower bound: if $$a_n=a_{n+1}$$, $$b_n-b_{n+1}=\frac{x}{n(n+1)}<1$$ and $$x < n^2+n=(n+\frac12)^2-\frac14$$. Solving for $$n$$ in terms of $$x$$, $$n > \sqrt{x+\frac14}-\frac12$$. Let $$N(x)=\left\lfloor\sqrt{x+\frac14}+\frac12\right\rfloor$$ be the first integer value that get us the inequality.

Now, for the upper bound. No matter how far we go, until $$a_n$$ drops all the way to zero, we still have the chance of $$a_n$$ and $$a_{n+1}$$ being different. Looking at one difference just won't be enough. Instead, we stack differences together; if $$a_n-a_{n+k} < k$$, then since $$a_n$$ is a decreasing sequence of integers, some two consecutive values in that range must be zero. By the other half of our key inequality, this is guaranteed to happen when $$b_n-b_{n+k} \le k-1$$. Start at the first possible place for two values to be equal; we're looking for the least $$k$$ such that $$b_{N(x)}-b_{N(x)+k} \le k-1$$. This inequality becomes $$k-1 \ge \frac{x}{N(x)}-\frac{x}{N(x)+k} = \frac{kx}{N(x)(N(x)+k)}$$ $$(k-1)N^2(x)+k(k-1)N(x) \ge kx$$ This is - well, it's a mess, because of the floor in the definition of $$N$$. So, we approximate - $$N(x) \le \sqrt{x+\frac14}+\frac12$$, so $$x \ge (N(x)-\frac12)^2-\frac14=N^2(x)-N(x)$$. Oops - we actually need a lower bound for $$x$$ here (see comments). If $$(k-1)N^2(x)+k(k-1)N(x) \ge k(N^2(x)+N(x))$$ $$(k^2+2k)N(x) \ge N^2(x)$$ $$N(X)\le (k+1)^2-1$$ then, since $$k(N^2(x)+N(x)) > kx$$, $$(k-1)N^2(x)+k(k-1)N(x) > kx$$ and we have a $$k$$ that works. This is true precisely when $$k>\sqrt{N(x)+1}-1$$; we will, of course, take the first successful value. The least $$n$$ with $$a_n=a_{n+1}$$ must satisfy $$\sqrt{x}\approx N(x) \le n \le N(x)+\lfloor\sqrt{N(x)+1}\rfloor-1$$ $$\le \left\lfloor\sqrt{x+\frac14}+\frac12\right\rfloor + \left\lfloor\sqrt{\sqrt{x+\frac14}+\frac32}\right\rfloor-1\approx \sqrt{x}+\sqrt[4]{x}$$

And now, for something new.

Where in that interval will it happen? For a randomly chosen $$x$$, it's essentially random - but biased. The deviation $$1-(b_n-b_{n+1})$$ increases approximately linearly with $$n$$ starting at zero for $$n=N(x)$$, so the sum of $$j$$ of them grows like $$j^2$$. The probability of our first duplication coming in the first $$j$$ chances is thus approximately proportional to $$j^2$$, and the location follows a wedge distribution; the probability of it being at $$N(x)+j$$ is approximately $$\frac{2j+1}{N(x)}$$ for $$0\le j<\sqrt{N(x)}$$.

But we can do better than that. Write $$N^2(x)=x+c$$; rearranging our inequalities $$N^2-N\le x< N^2+N$$, $$x-N(x) < N^2(x) \le x+N(x)$$ Then $$\frac{x}{N(x)}=\frac{N^2(x)+c}{N(x)}=N(x)+\frac{c}{N(x)}$$. This fractional part $$\frac{c}{N(x)}$$, between $$-1$$ and $$1$$, is what actually determines where in the interval we finally reach a spot with two consecutive $$a_n$$ equal. As we repeatedly subtract quantities slightly less than $$1$$ from $$b_n$$, its fractional part increases until it ticks over an integer - and when that happens, we get our first repeat in the $$a_n$$.

Let $$\frac{x}{N(x)+k}=N(x)-k+e_k$$. As already noted, $$e_0=\frac{c}{N(x)}\in [-1,1)$$. For $$e_0\in [-1,0)$$, we seek the first $$k$$ such that $$e_k \ge 0$$. For $$e_0\in [0,1)$$, we seek the first $$k$$ such that $$e_k \ge 1$$. We will then have $$a_{N(x)+k-1}=a_{N(x)+k}$$. Clear the denominator to get $$x = N^2(x) - k^2 + N(x)e_k + ke_k$$ $$0 = N(x)(e_k-e_0) + ke_k - k^2$$ $$k = \frac{e_k +\sqrt{k^2+4(e_k-e_0)N(x)}}{2}$$ For negative $$e_0$$, the key point comes when $$e_k\approx 0$$, and $$2k\approx \sqrt{k^2-4e_0 N(x)}$$, or $$3k^2\approx -4e_0 N(x)$$ and $$k\approx \frac{2}{\sqrt{3}}\sqrt{-e_0 N(x)}$$. For positive $$e_0$$, the key point comes when $$e_k\approx 1$$, and $$2k-1\approx \sqrt{k^2+4(1-e_0) N(x)}$$. Solve that to $$k\approx \frac{2}{\sqrt{3}}\sqrt{(1-e_0)N(x)}+\frac23$$.

So then, the amount $$k$$ we need to add to $$N(x)$$ is about $$\frac{2}{\sqrt{3}}\sqrt{N(x)}$$ times the square root of either $$-e_0$$ or $$1-e_0$$. It takes longest when $$e_0$$ is equal to $$-1$$ or $$0$$, at $$x=N^2-N$$ or $$x=N^2$$, and shortest when $$x$$ is slightly less than one of those values. And that's all I have to say on this one.

• Very good answer! Just one small error (not affecting the outcome): Given $x$ and $N(x)$, you want to find the smallest $k$ fulfilling $(k-1)N^2(x)+k(k-1)N(x) \ge kx$. You prove $x \ge N^2(x)-N(x)$, then plug this into the above, which is wrong. You want to find a $k$ that satisfies the first inequality. By lowering the RHS of that inequality, you are making it easier to satisfy that condition, so any $k$ value that satisfies it may not necessarily satisfy the original inequality. You need to consider $x < N^2(x)+N(x)$, plug that in, leading to $(k-1)^2>N(x)+1$, so an increase by only 1. – Ingix Jan 23 '19 at 8:31
• I know I spent time thinking on it the first time around... OK, edit incoming. – jmerry Jan 23 '19 at 9:00
• I see there constraints only. The full solution is in my answer. – Yuri Negometyanov Jan 28 '19 at 21:31

It cannot occur between term $$n$$ and term $$n+1$$ if $$\frac{x}{n} - \frac{x}{n+1} \ge 1$$, equivalently $$x \ge n^2 + n$$, equivalently $$n \le -\frac{1}{2} + \frac{\sqrt{1+4x}}{2}$$.

It must occur, either between term $$n$$ and $$n+1$$, or between term $$n+1$$ and $$n+2$$, if $$\frac{x}{n} - \frac{x}{n+1} \le \frac{1}{2}$$, equivalently $$x \le \frac{1}{2} n^2 + \frac{1}{2} n$$, equivalently $$n \ge -\frac{1}{2} + \frac{\sqrt{1+8x}}{2}$$.

So the first place it appears is somewhere between the two extremes of $$-\frac{1}{2} + \frac{\sqrt{1+4x}}{2}$$ and $$-\frac{1}{2} + \frac{\sqrt{1+8x}}{2} + 1 = \frac{1}{2} + \frac{\sqrt{1+8x}}{2}$$.

• Thank you for your answer! So it gives an estimate of the first occurence between $\sqrt{x}$ and $\sqrt{2} \sqrt{x}$. Sidenote: why $x/n - x/(n+1) \leq 1/2$? Couldn't it occur sooner, for example if $x/n - x/(n+1) = 0.75$? – Basj Jan 22 '19 at 14:46
• I think the point is it can occur sooner than when $x/n - x/(n+1) \leq 1/2.$ But it will certainly occur at about that point even if it does not occur sooner. – David K Jan 22 '19 at 14:52
• Is this exact solution, or constraints only? – Yuri Negometyanov Jan 28 '19 at 21:34

$$\color{brown}{\textbf{Preliminary Notes.}}$$

$$\dfrac xN > \dfrac x{N+1},$$ so the required equality $$\left\lfloor\dfrac xN\right\rfloor = \left\lfloor\dfrac x{N+1}\right\rfloor,\tag1$$ where $$\lfloor a\rfloor = \mathrm{floor}\,(a),$$
has solutions iff $$\left\{\dfrac xN\right\} > \left\{\dfrac x{N+1}\right\}.\tag2$$ Taking in account that $$k\left\{\dfrac xk\right\} = x\hspace{-12mu}\mod k,$$ inequality $$(2)$$ can be presented in the form of $$\dfrac{x\hspace{-12mu}\mod N}N > \dfrac{x\hspace{-12mu}\mod (N+1)}{N+1},\tag3$$ and from $$(3)$$ should $$x\hspace{-12mu}\mod N \ge x\hspace{-12mu}\mod (N+1).\tag4$$ Formula $$(4)$$ can be used for the testing, instead the issue one.

$$\color{brown}{\textbf{Decision.}}$$

The least solution $$N$$ of equality $$(1)$$ belongs to the interval $$x\in(n(n-1),n(n+1)],$$ so $$x=n(n-1)+m,\quad m=x-(n^2-n),\quad m\in[1,2n],\tag5$$ wherein $$n = \left\lceil\dfrac{\sqrt{4x-3}+1}2\right\rceil\tag6,$$ $$\lceil a\rceil = \mathrm{ceil}\,(a).$$

Let $$N=n+k,\quad k\in\mathbb N\tag7,$$ $$\dfrac xN = \dfrac{n^2-n+m}{n+k}=n-k-1+\dfrac{k(k+1)+m}{n+k},$$ $$\dfrac x{N+1} = \dfrac{n^2-n+m}{n+k+1}=n-k-2+\dfrac{(k+1)(k+2)+m}{n+k+1},$$

If $$\underline{m\in[1,n-1]}$$ then the least solution of $$(3)$$ can be achieved iff $$(k+1)(k+2)+m\ge n+k+1,\quad k =\left\lceil\sqrt{n-m}-1\right\rceil,$$ $$N = n - 1 + \left\lceil\sqrt{n^2-x}\right\rceil.$$

If $$\underline{m\in[n,2n-1]}$$ then the least solution of $$(3)$$ can be achieved iff $$(k+1)(k+2)+m\ge 2(n+k+1),\quad k^2+k-(2n-m)\geq 0,\quad k = \left\lceil\dfrac{\sqrt{8n-4m+1}-1}2\right\rceil,$$ $$N = n + \left\lceil\dfrac{\sqrt{4(n^2+n-x^2)+1}-1}2\right\rceil.$$

If $$\underline{m=2n}$$ then $$\dfrac xN = \dfrac{n^2+n}{n+k}=n-k+1+\dfrac{k(k-1)}{n+k},$$ $$\dfrac x{N+1} = \dfrac{n^2+n}{n+k+1}=n-k+\dfrac{k(k+1)}{n+k+1},$$ and the least solution of $$(3)$$ can be achieved iff $$k(k-1) $$N = n + \left\lceil\sqrt{n+1}\right\rceil.$$

$$\color{brown}{\textbf{Result.}}$$

Therefore, the least solution of $$(1)$$ is \boxed{\begin{align} &N=\begin{cases} n - 1 +\left\lceil\sqrt{n^2-x}\right\rceil,\quad\text{if}\quad x-n(n-1)\in[1,n-1]\\[4pt] n + \left\lceil\dfrac{\sqrt{4(n^2+n-x)+1}-1}2\right\rceil,\quad\text{if}\quad x-n(n-1)\in[n,2n-1]\\[4pt] n + \left\lceil\sqrt{n+1}\right\rceil,\quad\text{if}\quad x = n(n+1), \end{cases}\\ &\text{where}\\ &n = \left\lceil\dfrac{\sqrt{4x-3}+1}2\right\rceil. \end{align}}\tag8

$$\color{brown}{\textbf{Examples.}}$$

$$\underline{x=2475,\quad n=50,\quad x-n(n-1)=25}.$$

There is the first case of $$(8).$$

Result is $$N=54,$$ with $$\left\lfloor\dfrac{2475}{54}\right\rfloor = \left\lfloor\dfrac{2475}{55}\right\rfloor=45.$$

$$\underline{x=2500,\quad n=50,\quad x-n(n-1)=50}.$$

There is the second case of $$(8).$$

Result is $$N=57,$$ with $$\left\lfloor\dfrac{2500}{57}\right\rfloor = \left\lfloor\dfrac{2500}{58}\right\rfloor=43.$$

$$\underline{x=2450,\quad n=49,\quad x=n(n+1)}.$$

There is the third case of $$(8).$$

Result is $$N=57,$$ with $$\left\lfloor\dfrac{2450}{57}\right\rfloor = \left\lfloor\dfrac{2450}{58}\right\rfloor=42.$$

Proffering the following.

Let $$n$$ be an integer such that $$n^2-n\ge x$$. The smallest such $$n$$ is $$\approx\sqrt x$$.

Let $$k\ge \sqrt{n}$$ be an integer. Then we have $$\frac x{n}-\frac x{n+k}-(k-1)=\frac{kx-(k-1)n(n-k)}{n(n+k)}=\frac{k \left(-n^2+n+x\right)+\left(n^2-k^2n\right)}{n (k+n)}.$$ In the last form both expressions in parens in the numerator are negative. Therefore $$\frac x{n}-\frac x{n+k} So while the denominator $$m$$ increases from $$n$$ to $$n+k$$, the quotient $$x/m$$ decreases by less than $$k-1$$. This implies that $$\lfloor x/m \rfloor$$ can take at most $$k$$ values when $$m$$ covers the range $$[n,n+k]$$, $$k+1$$ choices, implying that a repetition took place somewhere in that interval.

Lee Mosher already explained why the repetition cannot happen sooner, so this is the first repetition.

The first repeated value of $$\lfloor x/m \rfloor$$ occurs somewhere when $$m$$ is in the interval roughly between $$x^{1/2}$$ and $$x^{1/2}+x^{1/4}$$, as first observed by jmerry. See their answer for more details about where within that range we can expect to see a repetition.

• Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from? – Basj Jan 22 '19 at 15:48
• @Basj $n\approx\sqrt x$, and $k\approx \sqrt n$. – Jyrki Lahtonen Jan 22 '19 at 15:50
• Anyway, the idea is to look at a wider range of denominators (instead ot just two consequtive ones), and select it smartly to force a repeated integer part of the quotient. – Jyrki Lahtonen Jan 22 '19 at 16:02