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

Question

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.

Please help with the problem.

Answer 1

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

Answer 2

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

Answer 3

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]