0%

Problem 585


Problem 585


Nested square roots

Consider the term $\small \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:
$\small \sqrt{3+\sqrt{2}+\sqrt{2}}=\sqrt{2}+\sqrt{1}=\sqrt{2}+1$
$\small \sqrt{8+\sqrt{15}+\sqrt{15}}=\sqrt{5}+\sqrt{3}$
$\small \sqrt{20+\sqrt{96}+\sqrt{12}}=\sqrt{9}+\sqrt{6}+\sqrt{3}-\sqrt{2}=3+\sqrt{6}+\sqrt{3}-\sqrt{2}$
$\small \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 $\small \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 \le n$. That is,
$\small \displaystyle \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\le n$.
Furthermore $y$ and $z$ are not allowed to be perfect squares.

Nested roots with the same value are not considered different, for example $\small \sqrt{7+\sqrt{3}+\sqrt{27}}$, $\small \sqrt{7+\sqrt{12}+\sqrt{12}}$ and $\small \sqrt{7+\sqrt{27}+\sqrt{3}}$, that can all three be denested into $\small 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).


嵌套平方根

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

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

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

记F($n$)为满足额外条件$0<x \le n$,且可以解套成有限个平方根的和或差的表达式$\small \sqrt{x+\sqrt{y}+\sqrt{z}}$的数目。也就是说,
$\small \displaystyle \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\le n$。
此外,$y$和$z$不能是完全平方数。

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

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