21
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – jmerry Jan 22 '19 at 14:33
  • $\begingroup$ Thank you for your comment @jmerry. Yes, an answer (that might give another estimate than the current answer) would be welcome! $\endgroup$ – Basj Jan 22 '19 at 14:48
  • $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Jan 22 '19 at 18:02
  • 1
    $\begingroup$ Exact solution obtained. $\endgroup$ – Yuri Negometyanov Jan 27 '19 at 16:51
  • $\begingroup$ oeis.org/A257213 is worth a look $\endgroup$ – Barry Cipra Mar 10 '19 at 15:33
13
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ingix Jan 23 '19 at 8:31
  • $\begingroup$ I know I spent time thinking on it the first time around... OK, edit incoming. $\endgroup$ – jmerry Jan 23 '19 at 9:00
  • $\begingroup$ I see there constraints only. The full solution is in my answer. $\endgroup$ – Yuri Negometyanov Jan 28 '19 at 21:31
10
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Basj Jan 22 '19 at 14:46
  • 3
    $\begingroup$ 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. $\endgroup$ – David K Jan 22 '19 at 14:52
  • $\begingroup$ Is this exact solution, or constraints only? $\endgroup$ – Yuri Negometyanov Jan 28 '19 at 21:34
6
+100
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from? $\endgroup$ – Basj Jan 22 '19 at 15:48
  • $\begingroup$ @Basj $n\approx\sqrt x$, and $k\approx \sqrt n$. $\endgroup$ – Jyrki Lahtonen Jan 22 '19 at 15:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jan 22 '19 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.