Problem 585

Nested square roots

Consider the term $\sqrt{x + \sqrt{y} + \sqrt{z}}$ that is representing a nested square root. $x$ , $y$ and $z$ are positive integers and $y$ and $z$ are not allowed to be perfect squares, so the number below the outer square root is irrational. Still it can be shown that for some combinations of $x$ , $y$ and $z$ the given term can be simplified into a sum and/or difference of simple square roots of integers, actually denesting the square roots in the initial expression.

Here are some examples of this denesting:
$\sqrt{3 + \sqrt{2} + \sqrt{2}} = \sqrt{2} + \sqrt{1} = \sqrt{2} + 1$
$\sqrt{8 + \sqrt{15} + \sqrt{15}} = \sqrt{5} + \sqrt{3}$
$\sqrt{20 + \sqrt{96} + \sqrt{12}} = \sqrt{9} + \sqrt{6} + \sqrt{3} - \sqrt{2} = 3 + \sqrt{6} + \sqrt{3} - \sqrt{2}$
$\sqrt{28 + \sqrt{160} + \sqrt{108}} = \sqrt{15} + \sqrt{6} + \sqrt{5} - \sqrt{2}$

As you can see the integers used in the denested expression may also be perfect squares resulting in further simplification.

Let F( $n$ ) be the number of different terms $\sqrt{x + \sqrt{y} + \sqrt{z}}$ , that can be denested into the sum and/or difference of a finite number of square roots, given the additional condition that $0 < x \leq n$ . That is,
$\sqrt{x + \sqrt{y} + \sqrt{z}} = \sum_{i = 1}^{k} s_{i} \sqrt{a_{i}}$
with $k$ , $x$ , $y$ , $z$ and all $a_{i}$ being positive integers, all $s_{i} = \pm 1$ and $x \leq n$ .
Furthermore $y$ and $z$ are not allowed to be perfect squares.

Nested roots with the same value are not considered different, for example $\sqrt{7 + \sqrt{3} + \sqrt{27}}$ , $\sqrt{7 + \sqrt{12} + \sqrt{12}}$ and $\sqrt{7 + \sqrt{27} + \sqrt{3}}$ , that can all three be denested into $2 + \sqrt{3}$ , would only be counted once.

You are given that F(10)=17, F(15)=46, F(20)=86, F(30)=213 and F(100)=2918 and F(5000)=11134074.
Find F(5000000).

嵌套平方根

考虑形如 $\sqrt{x + \sqrt{y} + \sqrt{z}}$ 所代表的嵌套平方根。 $x$ ， $y$ 和 $z$ 都是正整数，且 $y$ 和 $z$ 不能是完全平方数，因此最外层根号下的数是一个无理数。即便如此，可以看出仍然存在一些 $x$ ， $y$ 和 $z$ 的组合，使得这一式子能进一步简化为一系列简单整数平方根的和或差，或者说将最初的表达式中的平方根解套。

如下是一些解套的例子：
$\sqrt{3 + \sqrt{2} + \sqrt{2}} = \sqrt{2} + \sqrt{1} = \sqrt{2} + 1$
$\sqrt{8 + \sqrt{15} + \sqrt{15}} = \sqrt{5} + \sqrt{3}$
$\sqrt{20 + \sqrt{96} + \sqrt{12}} = \sqrt{9} + \sqrt{6} + \sqrt{3} - \sqrt{2} = 3 + \sqrt{6} + \sqrt{3} - \sqrt{2}$
$\sqrt{28 + \sqrt{160} + \sqrt{108}} = \sqrt{15} + \sqrt{6} + \sqrt{5} - \sqrt{2}$

可以看出，在解套之后的表达式中，根号下的整数可能是完全平方数，因此可以进一步简化。

记F( $n$ )为满足额外条件 $0 < x \leq n$ ，且可以解套成有限个平方根的和或差的表达式 $\sqrt{x + \sqrt{y} + \sqrt{z}}$ 的数目。也就是说，
$\sqrt{x + \sqrt{y} + \sqrt{z}} = \sum_{i = 1}^{k} s_{i} \sqrt{a_{i}}$
其中 $k$ ， $x$ ， $y$ ， $z$ 和所有的 $a_{i}$ 都是正整数，所有的 $s_{i} = \pm 1$ ，且 $x \leq n$ 。
此外， $y$ 和 $z$ 不能是完全平方数。

值相同的嵌套平方根视为相同的表达式，例如， $\sqrt{7 + \sqrt{3} + \sqrt{27}}$ ， $\sqrt{7 + \sqrt{12} + \sqrt{12}}$ 和 $\sqrt{7 + \sqrt{27} + \sqrt{3}}$ 都可以解套成 $2 + \sqrt{3}$ ，因此只被算入一次。

已知F(10)=17，F(15)=46，F(20)=86，F(30)=213，F(100)=2918以及F(5000)=11134074。
求F(5000000)。