Integer part of $(1 + \sqrt{2})^n$ [Solution]

The algorithm puzzle was to find the integer part of $(1 + \sqrt{2})^n$ using only integer arithmetic, in number of operations which is polynomial in $\log n$

[Note: the puzzle post mistakenly said time, instead of number of operations. Fixed now]

Solution

---

By the binomial theorem, notice that

$$(1 + \sqrt{2})^n = a_n + b_n \sqrt{2}$$

where $a_n$ and $b_n$ are both integers.

Now

$$(a_n + b_n \sqrt{2})(1 + \sqrt{2}) = (a_n + 2b_n) + (a_n +b_n)\sqrt{2}$$

Thus we get the recurrence relations:

$$a_{n+1} = a_n + 2b_n$$
$$b_{n+1} = a_n + b_n$$

This can be written in matrix form as

$$\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix} a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$

i.e.
$$A \begin{bmatrix}a_n\\b_n \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$

Giving us

$$A^n \begin{bmatrix}a_1\\b_1 \end{bmatrix} = \begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}$$

$A^n$ can be computed in $O(\log n)$ integer operations.

Once we have $(a_n, b_n)$ we can compute the integer part of $a_n + b_n \sqrt{2}$ by computing the integer part of $b_n \sqrt{2}$ using binary search for integer $x$ such that $x^2 \lt 2b_n^2 \lt (x+1)^2$ (or other algorithms) and adding that to $a_n$.

We could also solve this problem by a more straight-forward divide and conquer + memoization algorithm, like we did for Fibonacci earlier, by writing $(a_{2n}, b_{2n})$ in terms of $(a_n, b_n)$ etc.