Mixing
When does the first repetition in $;lfloor xrfloor, lfloor x/2 rfloor, lfloor x/3rfloor, lfloor x/4rfloor,...
$begingroup$
Let $lfloor xrfloor$ denote the floor of $x$.
When does the first repetition in $lfloor xrfloor$, $lfloor x/2rfloor$, $lfloor x/3rfloor$, $lfloor x/4rfloor$, ... 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, ...
number-theory elementary-number-theory
edited Jan 22 at 14:22
Blue
49k870156
asked Jan 22 at 13:56
BasjBasj
4071528
$endgroup$
add a comment |
$begingroup$
Let $lfloor xrfloor$ denote the floor of $x$.
When does the first repetition in $lfloor xrfloor$, $lfloor x/2rfloor$, $lfloor x/3rfloor$, $lfloor x/4rfloor$, ... 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, ...
number-theory elementary-number-theory
edited Jan 22 at 14:22
Blue
49k870156
asked Jan 22 at 13:56
BasjBasj
4071528
$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 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 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 at 18:02
1
$begingroup$
Exact solution obtained.
$endgroup$
– Yuri Negometyanov
Jan 27 at 16:51
$begingroup$
oeis.org/A257213 is worth a look
$endgroup$
– Barry Cipra
10 hours ago
add a comment |
$begingroup$
Let $lfloor xrfloor$ denote the floor of $x$.
When does the first repetition in $lfloor xrfloor$, $lfloor x/2rfloor$, $lfloor x/3rfloor$, $lfloor x/4rfloor$, ... 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, ...
number-theory elementary-number-theory
edited Jan 22 at 14:22
Blue
49k870156
asked Jan 22 at 13:56
BasjBasj
4071528
$endgroup$
Let $lfloor xrfloor$ denote the floor of $x$.
When does the first repetition in $lfloor xrfloor$, $lfloor x/2rfloor$, $lfloor x/3rfloor$, $lfloor x/4rfloor$, ... 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, ...
number-theory elementary-number-theory
number-theory elementary-number-theory
edited Jan 22 at 14:22
Blue
49k870156
asked Jan 22 at 13:56
BasjBasj
4071528
edited Jan 22 at 14:22
Blue
49k870156
asked Jan 22 at 13:56
BasjBasj
4071528
edited Jan 22 at 14:22
Blue
49k870156
edited Jan 22 at 14:22
Blue
49k870156
edited Jan 22 at 14:22
Blue
49k870156
49k870156
asked Jan 22 at 13:56
BasjBasj
4071528
asked Jan 22 at 13:56
BasjBasj
4071528
asked Jan 22 at 13:56
BasjBasj
4071528
4071528
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 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 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 at 18:02
1
$begingroup$
Exact solution obtained.
$endgroup$
– Yuri Negometyanov
Jan 27 at 16:51
$begingroup$
oeis.org/A257213 is worth a look
$endgroup$
– Barry Cipra
10 hours ago
add a comment |
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 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 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 at 18:02
1
$begingroup$
Exact solution obtained.
$endgroup$
– Yuri Negometyanov
Jan 27 at 16:51
$begingroup$
oeis.org/A257213 is worth a look
$endgroup$
– Barry Cipra
10 hours ago
2
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 at 14:33
$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 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 at 14:48
$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 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 at 18:02
$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 at 18:02
1
1
$begingroup$
Exact solution obtained.
$endgroup$
– Yuri Negometyanov
Jan 27 at 16:51
$begingroup$
Exact solution obtained.
$endgroup$
– Yuri Negometyanov
Jan 27 at 16:51
$begingroup$
oeis.org/A257213 is worth a look
$endgroup$
– Barry Cipra
10 hours ago
$begingroup$
oeis.org/A257213 is worth a look
$endgroup$
– Barry Cipra
10 hours ago
add a comment |
4 Answers
4
active
oldest
votes
$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 $leftlfloor frac xnrightrfloor$ 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 urfloor + lfloor vrfloorle lfloor u+vrfloor le lfloor urfloor + lceil vrceil$, 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)=leftlfloorsqrt{x+frac14}+frac12rightrfloor$$
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)+lfloorsqrt{N(x)+1}rfloor-1 $$
$$le leftlfloorsqrt{x+frac14}+frac12rightrfloor + leftlfloorsqrt{sqrt{x+frac14}+frac32}rightrfloor-1approx 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 $0le j<sqrt{N(x)}$.
But we can do better than that. Write $N^2(x)=x+c$; rearranging our inequalities $N^2-Nle 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_0in [-1,0)$, we seek the first $k$ such that $e_k ge 0$. For $e_0in [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_kapprox 0$, and $2kapprox sqrt{k^2-4e_0 N(x)}$, or $3k^2approx -4e_0 N(x)$ and $kapprox frac{2}{sqrt{3}}sqrt{-e_0 N(x)}$. For positive $e_0$, the key point comes when $e_kapprox 1$, and $2k-1approx sqrt{k^2+4(1-e_0) N(x)}$. Solve that to $kapprox 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.
answered Jan 22 at 21:54
jmerryjmerry
13k1628
$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 at 8:31
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
add a comment |
$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}$.
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
$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 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 at 14:52
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
add a comment |
$begingroup$
$color{brown}{textbf{Preliminary Notes.}}$
$dfrac xN > dfrac x{N+1},$ so the required equality
$$leftlfloordfrac xNrightrfloor = leftlfloordfrac x{N+1}rightrfloor,tag1$$
where $lfloor arfloor = mathrm{floor},(a),$
has solutions iff
$$left{dfrac xNright} > left{dfrac x{N+1}right}.tag2$$
Taking in account that
$$kleft{dfrac xkright} = xhspace{-12mu}mod k,$$
inequality $(2)$ can be presented in the form of
$$dfrac{xhspace{-12mu}mod N}N > dfrac{xhspace{-12mu}mod (N+1)}{N+1},tag3$$
and from $(3)$ should
$$xhspace{-12mu}mod N ge xhspace{-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 $xin(n(n-1),n(n+1)],$ so
$$x=n(n-1)+m,quad m=x-(n^2-n),quad min[1,2n],tag5$$
wherein
$$n = leftlceildfrac{sqrt{4x-3}+1}2rightrceiltag6,$$
$lceil arceil = mathrm{ceil},(a).$
Let
$$N=n+k,quad kinmathbb Ntag7,$$
$$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{min[1,n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge n+k+1,quad k =leftlceilsqrt{n-m}-1rightrceil,$$
$$N = n - 1 + leftlceilsqrt{n^2-x}rightrceil.$$
If $underline{min[n,2n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge 2(n+k+1),quad k^2+k-(2n-m)geq 0,quad k = leftlceildfrac{sqrt{8n-4m+1}-1}2rightrceil,$$
$$N = n + leftlceildfrac{sqrt{4(n^2+n-x^2)+1}-1}2rightrceil.$$
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 = leftlceilsqrt{n+1}rightrceil,$$
$$N = n + leftlceilsqrt{n+1}rightrceil.$$
$color{brown}{textbf{Result.}}$
Therefore, the least solution of $(1)$ is
$$boxed{begin{align}
&N=begin{cases}
n - 1 +leftlceilsqrt{n^2-x}rightrceil,quadtext{if}quad x-n(n-1)in[1,n-1]\[4pt]
n + leftlceildfrac{sqrt{4(n^2+n-x)+1}-1}2rightrceil,quadtext{if}quad x-n(n-1)in[n,2n-1]\[4pt]
n + leftlceilsqrt{n+1}rightrceil,quadtext{if}quad x = n(n+1),
end{cases}\
&text{where}\
&n = leftlceildfrac{sqrt{4x-3}+1}2rightrceil.
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 $leftlfloordfrac{2475}{54}rightrfloor = leftlfloordfrac{2475}{55}rightrfloor=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 $leftlfloordfrac{2500}{57}rightrfloor = leftlfloordfrac{2500}{58}rightrfloor=43.$
$underline{x=2450,quad n=49,quad x=n(n+1)}.$
There is the third case of $(8).$
Result is $N=57,$ with $leftlfloordfrac{2450}{57}rightrfloor = leftlfloordfrac{2450}{58}rightrfloor=42.$
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
$endgroup$
add a comment |
$begingroup$
Proffering the following.
Let $n$ be an integer such that $n^2-nge x$. The smallest such $n$ is $approxsqrt x$.
Let $kge 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+xright)+left(n^2-k^2nright)}{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.
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
$endgroup$
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 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 at 16:02
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3083192%2fwhen-does-the-first-repetition-in-lfloor-x-rfloor-lfloor-x-2-rfloor-lfl%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 $leftlfloor frac xnrightrfloor$ 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 urfloor + lfloor vrfloorle lfloor u+vrfloor le lfloor urfloor + lceil vrceil$, 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)=leftlfloorsqrt{x+frac14}+frac12rightrfloor$$
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)+lfloorsqrt{N(x)+1}rfloor-1 $$
$$le leftlfloorsqrt{x+frac14}+frac12rightrfloor + leftlfloorsqrt{sqrt{x+frac14}+frac32}rightrfloor-1approx 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 $0le j<sqrt{N(x)}$.
But we can do better than that. Write $N^2(x)=x+c$; rearranging our inequalities $N^2-Nle 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_0in [-1,0)$, we seek the first $k$ such that $e_k ge 0$. For $e_0in [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_kapprox 0$, and $2kapprox sqrt{k^2-4e_0 N(x)}$, or $3k^2approx -4e_0 N(x)$ and $kapprox frac{2}{sqrt{3}}sqrt{-e_0 N(x)}$. For positive $e_0$, the key point comes when $e_kapprox 1$, and $2k-1approx sqrt{k^2+4(1-e_0) N(x)}$. Solve that to $kapprox 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.
answered Jan 22 at 21:54
jmerryjmerry
13k1628
$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 at 8:31
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
add a comment |
$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 $leftlfloor frac xnrightrfloor$ 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 urfloor + lfloor vrfloorle lfloor u+vrfloor le lfloor urfloor + lceil vrceil$, 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)=leftlfloorsqrt{x+frac14}+frac12rightrfloor$$
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)+lfloorsqrt{N(x)+1}rfloor-1 $$
$$le leftlfloorsqrt{x+frac14}+frac12rightrfloor + leftlfloorsqrt{sqrt{x+frac14}+frac32}rightrfloor-1approx 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 $0le j<sqrt{N(x)}$.
But we can do better than that. Write $N^2(x)=x+c$; rearranging our inequalities $N^2-Nle 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_0in [-1,0)$, we seek the first $k$ such that $e_k ge 0$. For $e_0in [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_kapprox 0$, and $2kapprox sqrt{k^2-4e_0 N(x)}$, or $3k^2approx -4e_0 N(x)$ and $kapprox frac{2}{sqrt{3}}sqrt{-e_0 N(x)}$. For positive $e_0$, the key point comes when $e_kapprox 1$, and $2k-1approx sqrt{k^2+4(1-e_0) N(x)}$. Solve that to $kapprox 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.
answered Jan 22 at 21:54
jmerryjmerry
13k1628
$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 at 8:31
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
add a comment |
$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 $leftlfloor frac xnrightrfloor$ 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 urfloor + lfloor vrfloorle lfloor u+vrfloor le lfloor urfloor + lceil vrceil$, 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)=leftlfloorsqrt{x+frac14}+frac12rightrfloor$$
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)+lfloorsqrt{N(x)+1}rfloor-1 $$
$$le leftlfloorsqrt{x+frac14}+frac12rightrfloor + leftlfloorsqrt{sqrt{x+frac14}+frac32}rightrfloor-1approx 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 $0le j<sqrt{N(x)}$.
But we can do better than that. Write $N^2(x)=x+c$; rearranging our inequalities $N^2-Nle 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_0in [-1,0)$, we seek the first $k$ such that $e_k ge 0$. For $e_0in [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_kapprox 0$, and $2kapprox sqrt{k^2-4e_0 N(x)}$, or $3k^2approx -4e_0 N(x)$ and $kapprox frac{2}{sqrt{3}}sqrt{-e_0 N(x)}$. For positive $e_0$, the key point comes when $e_kapprox 1$, and $2k-1approx sqrt{k^2+4(1-e_0) N(x)}$. Solve that to $kapprox 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.
answered Jan 22 at 21:54
jmerryjmerry
13k1628
$endgroup$
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 $leftlfloor frac xnrightrfloor$ 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 urfloor + lfloor vrfloorle lfloor u+vrfloor le lfloor urfloor + lceil vrceil$, 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)=leftlfloorsqrt{x+frac14}+frac12rightrfloor$$
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)+lfloorsqrt{N(x)+1}rfloor-1 $$
$$le leftlfloorsqrt{x+frac14}+frac12rightrfloor + leftlfloorsqrt{sqrt{x+frac14}+frac32}rightrfloor-1approx 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 $0le j<sqrt{N(x)}$.
But we can do better than that. Write $N^2(x)=x+c$; rearranging our inequalities $N^2-Nle 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_0in [-1,0)$, we seek the first $k$ such that $e_k ge 0$. For $e_0in [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_kapprox 0$, and $2kapprox sqrt{k^2-4e_0 N(x)}$, or $3k^2approx -4e_0 N(x)$ and $kapprox frac{2}{sqrt{3}}sqrt{-e_0 N(x)}$. For positive $e_0$, the key point comes when $e_kapprox 1$, and $2k-1approx sqrt{k^2+4(1-e_0) N(x)}$. Solve that to $kapprox 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.
answered Jan 22 at 21:54
jmerryjmerry
13k1628
edited Jan 23 at 9:21
answered Jan 22 at 21:54
jmerryjmerry
13k1628
answered Jan 22 at 21:54
jmerryjmerry
13k1628
answered Jan 22 at 21:54
jmerryjmerry
13k1628
13k1628
$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 at 8:31
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
add a comment |
$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 at 8:31
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
$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 at 8:31
$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 at 8:31
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I know I spent time thinking on it the first time around... OK, edit incoming.
$endgroup$
– jmerry
Jan 23 at 9:00
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
$begingroup$
I see there constraints only. The full solution is in my answer.
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:31
add a comment |
$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}$.
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
$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 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 at 14:52
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
add a comment |
$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}$.
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
$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 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 at 14:52
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
add a comment |
$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}$.
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
$endgroup$
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}$.
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
answered Jan 22 at 14:36
Lee MosherLee Mosher
50.3k33787
50.3k33787
$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 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 at 14:52
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
add a comment |
$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 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 at 14:52
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
$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 at 14:46
$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 at 14:46
3
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 at 14:52
$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 at 14:52
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
$begingroup$
Is this exact solution, or constraints only?
$endgroup$
– Yuri Negometyanov
Jan 28 at 21:34
add a comment |
$begingroup$
$color{brown}{textbf{Preliminary Notes.}}$
$dfrac xN > dfrac x{N+1},$ so the required equality
$$leftlfloordfrac xNrightrfloor = leftlfloordfrac x{N+1}rightrfloor,tag1$$
where $lfloor arfloor = mathrm{floor},(a),$
has solutions iff
$$left{dfrac xNright} > left{dfrac x{N+1}right}.tag2$$
Taking in account that
$$kleft{dfrac xkright} = xhspace{-12mu}mod k,$$
inequality $(2)$ can be presented in the form of
$$dfrac{xhspace{-12mu}mod N}N > dfrac{xhspace{-12mu}mod (N+1)}{N+1},tag3$$
and from $(3)$ should
$$xhspace{-12mu}mod N ge xhspace{-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 $xin(n(n-1),n(n+1)],$ so
$$x=n(n-1)+m,quad m=x-(n^2-n),quad min[1,2n],tag5$$
wherein
$$n = leftlceildfrac{sqrt{4x-3}+1}2rightrceiltag6,$$
$lceil arceil = mathrm{ceil},(a).$
Let
$$N=n+k,quad kinmathbb Ntag7,$$
$$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{min[1,n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge n+k+1,quad k =leftlceilsqrt{n-m}-1rightrceil,$$
$$N = n - 1 + leftlceilsqrt{n^2-x}rightrceil.$$
If $underline{min[n,2n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge 2(n+k+1),quad k^2+k-(2n-m)geq 0,quad k = leftlceildfrac{sqrt{8n-4m+1}-1}2rightrceil,$$
$$N = n + leftlceildfrac{sqrt{4(n^2+n-x^2)+1}-1}2rightrceil.$$
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 = leftlceilsqrt{n+1}rightrceil,$$
$$N = n + leftlceilsqrt{n+1}rightrceil.$$
$color{brown}{textbf{Result.}}$
Therefore, the least solution of $(1)$ is
$$boxed{begin{align}
&N=begin{cases}
n - 1 +leftlceilsqrt{n^2-x}rightrceil,quadtext{if}quad x-n(n-1)in[1,n-1]\[4pt]
n + leftlceildfrac{sqrt{4(n^2+n-x)+1}-1}2rightrceil,quadtext{if}quad x-n(n-1)in[n,2n-1]\[4pt]
n + leftlceilsqrt{n+1}rightrceil,quadtext{if}quad x = n(n+1),
end{cases}\
&text{where}\
&n = leftlceildfrac{sqrt{4x-3}+1}2rightrceil.
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 $leftlfloordfrac{2475}{54}rightrfloor = leftlfloordfrac{2475}{55}rightrfloor=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 $leftlfloordfrac{2500}{57}rightrfloor = leftlfloordfrac{2500}{58}rightrfloor=43.$
$underline{x=2450,quad n=49,quad x=n(n+1)}.$
There is the third case of $(8).$
Result is $N=57,$ with $leftlfloordfrac{2450}{57}rightrfloor = leftlfloordfrac{2450}{58}rightrfloor=42.$
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
$endgroup$
add a comment |
$begingroup$
$color{brown}{textbf{Preliminary Notes.}}$
$dfrac xN > dfrac x{N+1},$ so the required equality
$$leftlfloordfrac xNrightrfloor = leftlfloordfrac x{N+1}rightrfloor,tag1$$
where $lfloor arfloor = mathrm{floor},(a),$
has solutions iff
$$left{dfrac xNright} > left{dfrac x{N+1}right}.tag2$$
Taking in account that
$$kleft{dfrac xkright} = xhspace{-12mu}mod k,$$
inequality $(2)$ can be presented in the form of
$$dfrac{xhspace{-12mu}mod N}N > dfrac{xhspace{-12mu}mod (N+1)}{N+1},tag3$$
and from $(3)$ should
$$xhspace{-12mu}mod N ge xhspace{-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 $xin(n(n-1),n(n+1)],$ so
$$x=n(n-1)+m,quad m=x-(n^2-n),quad min[1,2n],tag5$$
wherein
$$n = leftlceildfrac{sqrt{4x-3}+1}2rightrceiltag6,$$
$lceil arceil = mathrm{ceil},(a).$
Let
$$N=n+k,quad kinmathbb Ntag7,$$
$$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{min[1,n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge n+k+1,quad k =leftlceilsqrt{n-m}-1rightrceil,$$
$$N = n - 1 + leftlceilsqrt{n^2-x}rightrceil.$$
If $underline{min[n,2n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge 2(n+k+1),quad k^2+k-(2n-m)geq 0,quad k = leftlceildfrac{sqrt{8n-4m+1}-1}2rightrceil,$$
$$N = n + leftlceildfrac{sqrt{4(n^2+n-x^2)+1}-1}2rightrceil.$$
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 = leftlceilsqrt{n+1}rightrceil,$$
$$N = n + leftlceilsqrt{n+1}rightrceil.$$
$color{brown}{textbf{Result.}}$
Therefore, the least solution of $(1)$ is
$$boxed{begin{align}
&N=begin{cases}
n - 1 +leftlceilsqrt{n^2-x}rightrceil,quadtext{if}quad x-n(n-1)in[1,n-1]\[4pt]
n + leftlceildfrac{sqrt{4(n^2+n-x)+1}-1}2rightrceil,quadtext{if}quad x-n(n-1)in[n,2n-1]\[4pt]
n + leftlceilsqrt{n+1}rightrceil,quadtext{if}quad x = n(n+1),
end{cases}\
&text{where}\
&n = leftlceildfrac{sqrt{4x-3}+1}2rightrceil.
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 $leftlfloordfrac{2475}{54}rightrfloor = leftlfloordfrac{2475}{55}rightrfloor=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 $leftlfloordfrac{2500}{57}rightrfloor = leftlfloordfrac{2500}{58}rightrfloor=43.$
$underline{x=2450,quad n=49,quad x=n(n+1)}.$
There is the third case of $(8).$
Result is $N=57,$ with $leftlfloordfrac{2450}{57}rightrfloor = leftlfloordfrac{2450}{58}rightrfloor=42.$
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
$endgroup$
add a comment |
$begingroup$
$color{brown}{textbf{Preliminary Notes.}}$
$dfrac xN > dfrac x{N+1},$ so the required equality
$$leftlfloordfrac xNrightrfloor = leftlfloordfrac x{N+1}rightrfloor,tag1$$
where $lfloor arfloor = mathrm{floor},(a),$
has solutions iff
$$left{dfrac xNright} > left{dfrac x{N+1}right}.tag2$$
Taking in account that
$$kleft{dfrac xkright} = xhspace{-12mu}mod k,$$
inequality $(2)$ can be presented in the form of
$$dfrac{xhspace{-12mu}mod N}N > dfrac{xhspace{-12mu}mod (N+1)}{N+1},tag3$$
and from $(3)$ should
$$xhspace{-12mu}mod N ge xhspace{-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 $xin(n(n-1),n(n+1)],$ so
$$x=n(n-1)+m,quad m=x-(n^2-n),quad min[1,2n],tag5$$
wherein
$$n = leftlceildfrac{sqrt{4x-3}+1}2rightrceiltag6,$$
$lceil arceil = mathrm{ceil},(a).$
Let
$$N=n+k,quad kinmathbb Ntag7,$$
$$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{min[1,n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge n+k+1,quad k =leftlceilsqrt{n-m}-1rightrceil,$$
$$N = n - 1 + leftlceilsqrt{n^2-x}rightrceil.$$
If $underline{min[n,2n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge 2(n+k+1),quad k^2+k-(2n-m)geq 0,quad k = leftlceildfrac{sqrt{8n-4m+1}-1}2rightrceil,$$
$$N = n + leftlceildfrac{sqrt{4(n^2+n-x^2)+1}-1}2rightrceil.$$
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 = leftlceilsqrt{n+1}rightrceil,$$
$$N = n + leftlceilsqrt{n+1}rightrceil.$$
$color{brown}{textbf{Result.}}$
Therefore, the least solution of $(1)$ is
$$boxed{begin{align}
&N=begin{cases}
n - 1 +leftlceilsqrt{n^2-x}rightrceil,quadtext{if}quad x-n(n-1)in[1,n-1]\[4pt]
n + leftlceildfrac{sqrt{4(n^2+n-x)+1}-1}2rightrceil,quadtext{if}quad x-n(n-1)in[n,2n-1]\[4pt]
n + leftlceilsqrt{n+1}rightrceil,quadtext{if}quad x = n(n+1),
end{cases}\
&text{where}\
&n = leftlceildfrac{sqrt{4x-3}+1}2rightrceil.
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 $leftlfloordfrac{2475}{54}rightrfloor = leftlfloordfrac{2475}{55}rightrfloor=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 $leftlfloordfrac{2500}{57}rightrfloor = leftlfloordfrac{2500}{58}rightrfloor=43.$
$underline{x=2450,quad n=49,quad x=n(n+1)}.$
There is the third case of $(8).$
Result is $N=57,$ with $leftlfloordfrac{2450}{57}rightrfloor = leftlfloordfrac{2450}{58}rightrfloor=42.$
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
$endgroup$
$color{brown}{textbf{Preliminary Notes.}}$
$dfrac xN > dfrac x{N+1},$ so the required equality
$$leftlfloordfrac xNrightrfloor = leftlfloordfrac x{N+1}rightrfloor,tag1$$
where $lfloor arfloor = mathrm{floor},(a),$
has solutions iff
$$left{dfrac xNright} > left{dfrac x{N+1}right}.tag2$$
Taking in account that
$$kleft{dfrac xkright} = xhspace{-12mu}mod k,$$
inequality $(2)$ can be presented in the form of
$$dfrac{xhspace{-12mu}mod N}N > dfrac{xhspace{-12mu}mod (N+1)}{N+1},tag3$$
and from $(3)$ should
$$xhspace{-12mu}mod N ge xhspace{-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 $xin(n(n-1),n(n+1)],$ so
$$x=n(n-1)+m,quad m=x-(n^2-n),quad min[1,2n],tag5$$
wherein
$$n = leftlceildfrac{sqrt{4x-3}+1}2rightrceiltag6,$$
$lceil arceil = mathrm{ceil},(a).$
Let
$$N=n+k,quad kinmathbb Ntag7,$$
$$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{min[1,n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge n+k+1,quad k =leftlceilsqrt{n-m}-1rightrceil,$$
$$N = n - 1 + leftlceilsqrt{n^2-x}rightrceil.$$
If $underline{min[n,2n-1]}$ then the least solution of $(3)$ can be achieved iff
$$(k+1)(k+2)+mge 2(n+k+1),quad k^2+k-(2n-m)geq 0,quad k = leftlceildfrac{sqrt{8n-4m+1}-1}2rightrceil,$$
$$N = n + leftlceildfrac{sqrt{4(n^2+n-x^2)+1}-1}2rightrceil.$$
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 = leftlceilsqrt{n+1}rightrceil,$$
$$N = n + leftlceilsqrt{n+1}rightrceil.$$
$color{brown}{textbf{Result.}}$
Therefore, the least solution of $(1)$ is
$$boxed{begin{align}
&N=begin{cases}
n - 1 +leftlceilsqrt{n^2-x}rightrceil,quadtext{if}quad x-n(n-1)in[1,n-1]\[4pt]
n + leftlceildfrac{sqrt{4(n^2+n-x)+1}-1}2rightrceil,quadtext{if}quad x-n(n-1)in[n,2n-1]\[4pt]
n + leftlceilsqrt{n+1}rightrceil,quadtext{if}quad x = n(n+1),
end{cases}\
&text{where}\
&n = leftlceildfrac{sqrt{4x-3}+1}2rightrceil.
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 $leftlfloordfrac{2475}{54}rightrfloor = leftlfloordfrac{2475}{55}rightrfloor=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 $leftlfloordfrac{2500}{57}rightrfloor = leftlfloordfrac{2500}{58}rightrfloor=43.$
$underline{x=2450,quad n=49,quad x=n(n+1)}.$
There is the third case of $(8).$
Result is $N=57,$ with $leftlfloordfrac{2450}{57}rightrfloor = leftlfloordfrac{2450}{58}rightrfloor=42.$
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
edited Jan 30 at 12:48
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
answered Jan 27 at 16:44
Yuri NegometyanovYuri Negometyanov
11.9k1729
11.9k1729
add a comment |
add a comment |
$begingroup$
Proffering the following.
Let $n$ be an integer such that $n^2-nge x$. The smallest such $n$ is $approxsqrt x$.
Let $kge 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+xright)+left(n^2-k^2nright)}{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.
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
$endgroup$
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 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 at 16:02
add a comment |
$begingroup$
Proffering the following.
Let $n$ be an integer such that $n^2-nge x$. The smallest such $n$ is $approxsqrt x$.
Let $kge 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+xright)+left(n^2-k^2nright)}{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.
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
$endgroup$
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 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 at 16:02
add a comment |
$begingroup$
Proffering the following.
Let $n$ be an integer such that $n^2-nge x$. The smallest such $n$ is $approxsqrt x$.
Let $kge 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+xright)+left(n^2-k^2nright)}{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.
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
$endgroup$
Proffering the following.
Let $n$ be an integer such that $n^2-nge x$. The smallest such $n$ is $approxsqrt x$.
Let $kge 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+xright)+left(n^2-k^2nright)}{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.
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
edited Jan 23 at 6:05
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
answered Jan 22 at 15:40
Jyrki LahtonenJyrki Lahtonen
110k13171380
110k13171380
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 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 at 16:02
add a comment |
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 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 at 16:02
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
Thank you! Just for completeness, from which line of your argument does the $x^{1/4}$ come from?
$endgroup$
– Basj
Jan 22 at 15:48
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 at 15:50
$begingroup$
@Basj $napproxsqrt x$, and $kapprox sqrt n$.
$endgroup$
– Jyrki Lahtonen
Jan 22 at 15:50
1
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 at 16:02
$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 at 16:02
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3083192%2fwhen-does-the-first-repetition-in-lfloor-x-rfloor-lfloor-x-2-rfloor-lfl%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 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 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 at 18:02
1
$begingroup$
Exact solution obtained.
$endgroup$
– Yuri Negometyanov
Jan 27 at 16:51
$begingroup$
oeis.org/A257213 is worth a look
$endgroup$
– Barry Cipra
10 hours ago