Задача 585
Вложенные квадратные корни

Рассмотрим выражение $\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$) будет количеством различных выражений $\small \sqrt{x+\sqrt{y}+\sqrt{z}}$, которые могут быть разложены в сумму и/или разность конечного количества квадратных корней с дополнительным условием, что $0<x \le n$. То есть,
$\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).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net