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

Question

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, ...

Answer 1

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}$.

Answer 2

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}<k-1. $$ 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.

Answer 3

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.

Answer 4

$\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+k,\quad (k-1)^2<n+1,\quad k = \left\lceil\sqrt{n+1}\right\rceil,$$ $$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.$