# Find $n$ such that $n\sqrt5 - \lfloor{n\sqrt5}\rfloor$ is maximised or minimised?

This question is from number theory :

Set $$n\in (1,2009)$$, and $$n$$ is a natural number. Find the values of $$n$$ such that $$n\sqrt5 - \lfloor{n\sqrt5}\rfloor$$ is minimised and maximised respectively.

I tried to convert the expression into an inequality as such:

$$m^2<5n^2<(m+1)^2$$ With $$m = \lfloor n\sqrt5\rfloor$$. This came to no avail.

I have also tried to set $$k = n\sqrt5 - \lfloor{n\sqrt5}\rfloor$$. This way, to maximise $$k$$, we maximise:

$$k(k+2m) = 5n^2-m^2$$

$$n = \frac{k+m}{\sqrt5}$$ But this also turns out to not work. I tried plotting the function and testing for different values of n. Apparently, for $$17$$, the value of the function seems quite minimal, and for $$21$$ it appears to be more maximal. I have noticed that smaller numbers tend to be more extreme for this function, as$$34 = 17\times2$$ is also quite minimal, but not so much as $$17$$. This appears to show a link, but I cannot identify it.

• probably has to do with the continued fraction representation of $\sqrt{5}$ Nov 8, 2019 at 14:50
• The first few convergents for $\sqrt 5$ are $\{2, \frac 94, \frac {38}{17}, \frac {161}{72}, \frac {682}{305}, \frac {2889}{1292}\}$. Taking the last one, we look at $n=1292$ and get $0.9998\cdots$ for your expression
– lulu
Nov 8, 2019 at 15:07
• There is an algorithm given in Wikipedia to find the answer. It starts with the continued fraction and reduces the last term until the denominator is small enough. You can't reduce the last term by more than half. I haven't tried it for your example. Nov 8, 2019 at 15:31
• @lulu you should aldo consider the convergents formed when you add $1$ to the last layer you keep, thus $[3]=3, [2;5]=11/5, [2;4,5]=47/21$, etc. The correct lower bound on $\sqrt{5}$ for this problem, $3571/1597$, comes from this sequence. Nov 8, 2019 at 19:30
• @OscarLanzi Ah, thank you.
– lulu
Nov 8, 2019 at 19:46

Another method is to use the familiar Fibonacci approximants for $$\phi=(1+\sqrt{5})/2$$. Rendering $$\sqrt{5}=2\phi-1$$, carry the upper bounds until you get a maximum odd denominator $$\le 2009$$, or a maximum even denominator $$\le 2×2009$$, and take whichever is later:

$$\frac{2}{1},\frac{5}{3},\frac{13}{8},...\frac{1597}{987},\color{blue}{\frac{4181}{2584}}$$

Do the same with the lower bounds:

$$\frac{1}{1},\frac{3}{2},\frac{8}{5},...\frac{987}{610},\color{blue}{\frac{2584}{1597}}$$

So the optimal bounds within the problem constraints are:

$$\frac{2584}{1597}<\phi<\frac{4181}{2584}$$

and with $$\sqrt{5}=2\phi-1$$:

$$\frac{3571}{1597}<\sqrt{5}<\frac{2889}{1292}$$.

• How do you necessarily do the Fibonacci approximants? Nov 10, 2019 at 3:48

Locating a real number in the Stern–Brocot tree gives good rational approximations with increasing denominators.

For $$\sqrt5$$, below is the output for denominators at most $$2009$$. The last line says that the best approximations with this restriction on denominators are $$3571/1597$$ and $$2889/1292$$. The denominators in these two fractions are the ones you seek. You just need to test which is which.

$$\begin{array}{rrrrr} n& a& b& c& d& \\ 1& 1& 1& 1& 0 \\ 2& 2& 1& 1& 0 \\ 3& 2& 1& 3& 1 \\ 4& 2& 1& 5& 2 \\ 5& 2& 1& 7& 3 \\ 6& 2& 1& 9& 4 \\ 7& 11& 5& 9& 4 \\ 8& 20& 9& 9& 4 \\ 9& 29& 13& 9& 4 \\ 10& 38& 17& 9& 4 \\ 11& 38& 17& 47& 21 \\ 12& 38& 17& 85& 38 \\ 13& 38& 17& 123& 55 \\ 14& 38& 17& 161& 72 \\ 15& 199& 89& 161& 72 \\ 16& 360& 161& 161& 72 \\ 17& 521& 233& 161& 72 \\ 18& 682& 305& 161& 72 \\ 19& 682& 305& 843& 377 \\ 20& 682& 305& 1525& 682 \\ 21& 682& 305& 2207& 987 \\ 22& 682& 305& 2889& 1292 \\ 23& 3571& 1597& 2889& 1292 \\ \end{array}$$ Here is Python code to generate this table:

from math import sqrt
t=sqrt(5)
a,b=0,1
c,d=1,0
n=0
while 1:
n=n+1
e=a+c
f=b+d
s=(e+0.0)/f
if s<t:
a,b=e,f
else:
c,d=e,f
print(n,a,b,c,d)
if b>2009 or d>2009:
break

• You can modify the contjnued fraction appriachvto get thus tree. See my comment to the question. Nov 8, 2019 at 19:35

The convergents of the continued fraction seem to me the best approach. However, one should also consider the generalized convergents. Here are the convergents of the cont frac of $$\sqrt 5$$:

       2       1
9       4
38      17
161      72
682     305
2889    1292
12238    5473
51841   23184
219602   98209
930249  416020
...       ...


Here are the running minima and maxima of $$\{n \cdot \sqrt 5 \}$$

     n      frac(n*sqrt(5))   running minima running maxima
------------------------------------------------------------
**   1     0.236067977500     0.236067977500  0.236067977500
2     0.472135955000     0.236067977500  0.472135955000
3     0.708203932499     0.236067977500  0.708203932499
**   4     0.944271909999     0.236067977500  0.944271909999
*   5     0.180339887499     0.180339887499  0.944271909999
*   9     0.124611797498     0.124611797498  0.944271909999
*  13    0.0688837074973    0.0688837074973  0.944271909999
**  17    0.0131556174964    0.0131556174964  0.944271909999
21     0.957427527496    0.0131556174964  0.957427527496
38     0.970583144992    0.0131556174964  0.970583144992
55     0.983738762488    0.0131556174964  0.983738762488
** 72     0.996894379985    0.0131556174964  0.996894379985
*  89    0.0100499974813    0.0100499974813  0.996894379985
* 161   0.00694437746614   0.00694437746614  0.996894379985
* 233   0.00383875745100   0.00383875745100  0.996894379985
** 305  0.000733137435857  0.000733137435857  0.996894379985
377     0.997627517421  0.000733137435857  0.997627517421
682     0.998360654857  0.000733137435857  0.998360654857
987     0.999093792292  0.000733137435857  0.999093792292
**1292     0.999826929728  0.000733137435857  0.999826929728
*1597  0.000560067164145  0.000560067164145  0.999826929728


Legend:

• ** : n taken from convergents of the cont frac (second column!)
either running minimum or running maximum improves
• * : n taken from generalized convergents (only where running minimum improves are marked.

Because the limit for $$n$$ in your problem-definition is not identical with an entry from the convergents, the generalized convergents might point to an improvement, which does not occur in the truncation of the sequence of convergents.

And we have $$n=1597$$ a minimum which was not detected by the original convergents only.

Here are the two types of generalized convergents ($$n$$ is taken from the second column):

[2, 1]   -  convergent
[11, 5]   - generalized for minimum
[20, 9]   - generalized for minimum
[29, 13]   - generalized for minimum
[38, 17]   -  convergent
[199, 89]   - generalized for minimum
[360, 161]   ...
[521, 233]
[682, 305]
[3571, 1597]
[6460, 2889]
[9349, 4181]
[12238, 5473]
[64079, 28657]
[115920, 51841]
[167761, 75025]
[219602, 98209]

[9, 4]   -  convergent
[47, 21]   - generalized for maximum
[85, 38]   - ...
[123, 55]
[161, 72]
[843, 377]
[1525, 682]
[2207, 987]
[2889, 1292]
[15127, 6765]
[27365, 12238]
[39603, 17711]
[51841, 23184]
[271443, 121393]
[491045, 219602]
[710647, 317811]
[930249, 416020]