How do find $\lfloor n\sqrt 7 \rfloor$ without a calculator

Question

For all positive integers, $n$, define $t_n = \lfloor n\sqrt 7 \rfloor$. I am trying to find a way to compute the values $t_n$ without squaring "large numbers" or taking square roots to more than the first few significant digits. The first 20 values are

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$t_n$	2	5	7	10	13	15	18	21	23	26	29	31	34	37	39	42	44	47	50	52

1. The OEIS says that this is a Beatty sequence. A consequence of that is, if $s=\sqrt 7$ and $t$ satisfies $\frac 1s + \frac 1t = 1$, then the images of the sequences $\{ns\}_{n=1}^\infty$ and $\{nt\}_{n=1}^\infty$ have no points in common and their union is the set of positive integers. I couldn't find a way to exploit that.

2. I also noticed that if $p$ is a common divisor of $n$ and of $t_n$, then $t_{n/p} = (t_n)/p$. But this is pointing in the wrong direction.

3. Also, since $2 < \sqrt 7 < 3$, then $t_{n+1} \in \{t_n + 2, t_n + 3 \}$. But I haven't figured out a simple way to decide which of the two is the correct value.

added 9/24/2021

I have worked out a partial answer which I will describe below.

---

Theorem. Let $A$ and $B$ be positive rational numbers, Let $n$ be a positive integer and let $p$ be a square-free positive integer. If $A < x < B$, then
$$ pn^2+AB < (A+B)n\sqrt p < pn^2 + AB + \dfrac 14(B-A)^2 $$
and, if $(B-A)^2 \le 4$,
$$ \lfloor (A+B)n\sqrt p \rfloor = pn^2+AB$$

---

*Proof

Suppose $A < n\sqrt p < B$.

For positive, rational numbers, $A$ and $B$, and for positive integer, $n$, consider the inverted parabola

$$y = (x-A)(B-x) = -x^2+(A+B)x – AB$$

For $A < x < B$, this function is positive valued with a max value of
$y_{max} = \dfrac 14(B-A)^2$ occurring at $x_{max}= \dfrac 12(A+B)$. It follows that

$$ 0 < (n\sqrt p – A)(B – \sqrt p) \lt y_{max} $$

We do not have to say $“\le"$ because $x = n\sqrt p$ is an irrational number and $x_{max}$ is a rational number. We continue.

$$ 0 < -pn^2 + (A+B)n\sqrt p -AB < \dfrac 14(B-A)^2 $$

$$ pn^2+AB < (A+B)n\sqrt p < pn^2 + AB + \dfrac 14(B-A)^2 $$

If $\dfrac 14(B-A)^2 \le 1$, it follows that
$$\lfloor (A+B)n\sqrt p \rfloor = pn^2+AB$$

So, for example, we know that $ 52 < 20\sqrt 7 < 53$.
Letting $A=52$, $B=53$, $p=7$, and $n=20$, we find that

$$ 5556 < 2100\sqrt 7 < 5556\dfrac 14 $$

We find by computation that $2100\sqrt 7 \approx 5556.077753$.

It follows immediately that

\begin{align}
\lfloor 2100\sqrt 7 \rfloor &= 5556 \\
\lfloor 4200\sqrt 7 \rfloor &= 11112\\
\lfloor 6300\sqrt 7 \rfloor &= 16668 \\
\lfloor 8400\sqrt 7 \rfloor &= 22224 \\
\end{align}

Answer 1

If you compute a continued fraction approximation $\sqrt 7 \approx \frac pq$, then for a while, you can compute $\lfloor n \sqrt 7\rfloor$ by computing $\lfloor \frac{pn}{q}\rfloor$ instead. This is very quick if we're computing the entire sequence: if we know $\hat t_n = \lfloor \frac{pn}{q}\rfloor$ and saved the value of $r_n = pn \bmod q$, then $$ r_{n+1} = r_n + p \bmod q\qquad \text{ and } \qquad \hat t_{n+1} = t_n + \left\lfloor\frac{r_n + p}{q}\right\rfloor = \hat t_n + \frac{p + r_n - r_{n+1}}{q}. $$ Even if you want just one term $t_n$, $\lfloor \frac{pn}{q}\rfloor$ is not too terrible to compute - it's just that computing the entire sequence $t_1, t_2, \dots, t_n$ is where the approximation really shines.

---

However, at some point, the approximation stops working.

In general, we can guarantee that $\lfloor \frac{pn}{q}\rfloor = \lfloor n\sqrt 7\rfloor$ for $n < q$. That's because $|\frac pq - \sqrt 7| < \frac1{q^2}$ for all continued fraction approximations, so $|\frac{pn}{q} - n\sqrt 7| < \frac{n}{q^2} < \frac1q$. As long as $\frac{pn}{q}$ is not an integer, it will be at least $\frac 1q$ away from the nearest integer, and $n\sqrt 7$ is closer than that.

So all you have to do to compute the sequence $t_n$ is to keep computing better and better continued fraction approximations to $\sqrt 7$. We have $$ \sqrt 7 = 2 + \cfrac1{1 + \cfrac1{1 + \cfrac 1{1 + \cfrac1{4 + \dotsb}}}} $$ and the block $1,1,1,4$ repeats forever; in continued fraction notation, $\sqrt 7 = [2; \overline{1,1,1,4}]$. There is a recursive formula for the $n^{\text{th}}$ continued fraction approximation: starting from $\frac{p_{-2}}{q_{-2}} = \frac 01$ and $\frac{p_{-1}}{q_{-1}} = \frac10$, we have $$\frac{p_n}{q_n} = \frac{a_n p_{n-1} + p_{n-2}}{a_n q_{n-1} + q_{n-2}}$$ where $a_n$ is the $n^{\text{th}}$ term of the periodic sequence $2, 1, 1, 1, 4, 1, 1, 1, 4, \dots$. To check yourself, the next few fractions you get are $$\frac 21, \frac31, \frac52, \frac83, \frac{37}{14}, \frac{45}{17}, \dots$$

Since the denominators $q_n$ grow exponentially, you will not have to do this very often if you want to compute your sequence; to compute $t_1, t_2, \dots, t_n$, you'll only need to update the continued fraction $O(\log n)$ times. (You could also begin by finding a continued fraction approximation $\sqrt 7 \approx \frac pq$ where $q$ is large enough to work for all the terms you want, then use that from the start.)