# 题目

## 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 < xn. That is,
$\sqrt{x+\sqrt{y}+\sqrt{z}}=\sum_{i=1}^ks_i\sqrt{a_i}$
with k, x, y, z and all ai being positive integers, all si = ±1 and xn.
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).

# 分析

1. $i+\sqrt{b}=\sqrt{(i^2+b)+\sqrt{i^2b}+\sqrt{i^2b}},0
i = 1, b = 2 时，就是题目中的第 1 个例子。
2. $\sqrt{a}+\sqrt{b}=\sqrt{(a+b)+\sqrt{ab}+\sqrt{ab}},1
a = 3, b = 5 时，就是题目中的第 2 个例子。
3. $-1+\sqrt{c}+\sqrt{a}+\sqrt{ac}=\sqrt{(a+1)(c+1)+\sqrt{4c(a-1)^2}+\sqrt{4a(c-1)^2}},$ $c>a>1,\hspace{0.5em}a,c,c/a\ne{k^2}$
4. $-i+\sqrt{c}+i\sqrt{a}+\sqrt{ac}=\sqrt{(a+1)(c+i^2)+\sqrt{4i^2c(a-1)^2}+\sqrt{4a(c-i^2)^2}},$ $a>1,c>i^2>1,a\ne{c},\hspace{0.5em}a,c,c/a,a/c\ne{k^2}$
Update: i = 2, c = 6, a = 2.5 也是可以的。
5. $-\sqrt{b}+\sqrt{c}+\sqrt{ab}+\sqrt{ac}=\sqrt{(a+1)(c+b)+\sqrt{4bc(a-1)^2}+\sqrt{4a(c-b)^2}},$ $a>1,c>b>1,\hspace{0.5em}a,b,c,c/b,ac/b\ne{k^2}$
a = 3, b = 2, c = 3 时，就是题目中的第 3 个例子。
a = 3, b = 2, c = 5 时，就是题目中的第 4 个例子。
Update: a = 1.5, b = 6, c = 8 也是可以的。

Update: 使用 SymPy，得到以下几个不属于前面 5 种情形的例子：
$-2+\sqrt{6}+\sqrt{10}+\sqrt{15}=\sqrt{35+\sqrt{40}+\sqrt{216}}$
$-\sqrt{6}+\sqrt{8}+3+\sqrt{12}=\sqrt{35+\sqrt{24}+\sqrt{48}}$
$-\sqrt{6}+3+\sqrt{10}+\sqrt{15}=\sqrt{40+\sqrt{60}+\sqrt{96}}$
$-\sqrt{8}+\sqrt{10}+\sqrt{12}+\sqrt{15}=\sqrt{45+\sqrt{24}+\sqrt{80}}$
$-\sqrt{10}+\sqrt{12}+\sqrt{15}+\sqrt{18}=\sqrt{55+\sqrt{24}+\sqrt{120}}$

# 不成功的解答

 1: #include <stdio.h>
2: #include <math.h>
3:
4: int isSquare(int n) { double x = sqrt(n); return x == (int)x; }
5: int max(int a, int b) { return (a > b) ? a : b; }
6:
7: int count(int b, int c0, int c9)
8: { // count: c in (c0, c9]; c,c/b != k^2
9:   return c9 - (int)sqrt(c9) - (int)sqrt(c9/b)
10:        - c0 + (int)sqrt(c0) + (int)sqrt(c0/b);
11: }
12:
13: int count4(int a, int b, int c0, int c9)
14: { // count: c in (c0, c9]; c,c/b,ac/b != k^2
15:   int z = 0;
16:   for (int d, c = c0 + 1; c <= c9; c++) {
17:     if (isSquare(c)) continue;
18:     if (c % b == 0 && isSquare(c / b)) continue;
19:     if ((d = a * c) % b == 0 && isSquare(d / b)) continue;
20:     z++;
21:   }
22:   return z;
23: }
24:
25: long f2a(int n)
26: { // i + √b: 0 < i, 1 < b != k^2
27:   long z = 0;    // i^2 + b <= n
28:   for (int b, i = 1; 1 < (b = n - i * i); i++)
29:     z += b - (int)sqrt(b);
30:   return z;
31: }
32:
33: long f2b(int n)
34: { // √a + √b: 1 < a < b; a,b,b/a != k^2
35:   long z = 0;             // a + b <= n
36:   for (int b, a = 2; a < (b = n - a); a++)
37:     if (!isSquare(a)) z += count(a, a, b);
38:   return z;
39: }
40:
41: long f4a(int n)
42: { // -1 + √c + √a + √(ac): c > a > 1; a,c,c/a != k^2
43:   long z = 0;                 // (a + 1)(c + 1) <= n
44:   for (int c, a = 2; a < (c = n / (a + 1) - 1); a++)
45:     if (!isSquare(a)) z += count(a, a, c);
46:   return z;
47: }
48:
49: long f4b(int n)
50: { // -i + √c + i√a + √(ac):   c > i^2 > 1; a,c != k^2
51:   long z = 0; // a != c, a > 1, (a + 1)(c + i^2) <= n
52:   for (int i2, i = 2; (i2 = i * i) * 2 * 3 <= n; i++) {
53:     for (int b, c, a = 2; (b = max(a,i2)) < (c = n/(a+1)-i2); a++)
54:       if (!isSquare(a)) z += count(a, b, c); // c > a; c/a != k^2
55:     for (int a, c = i2 + 1; c < (a = n / (i2 + c) - 1); c++)
56:       if (!isSquare(c)) z += count(c, c, a); // a > c; a/c != k^2
57:   }
58:   return z;
59: }
60:
61: long f4c(int n)
62: { // -√b + √c + √(ab) + √(ac):   a,b,c,c/b,ac/b != k^2
63:   long z = 0; // a > 1, c > b > 1, (a + 1)(b + c) <= n
64:   for (int a = 2; 5 * (a + 1) <= n; a++)
65:     if (!isSquare(a)) // a == (b or c) is allowed
66:       for (int c, b = 2; b < (c = n / (a + 1) - b); b++)
67:         if (!isSquare(b)) z += count4(a, b, b, c);
68:   return z;
69: }
70:
71: long f(int n)
72: {
73:   return f2a(n) + f2b(n) + f4a(n) + f4b(n) + f4c(n);
74: }
75:
76: int main()
77: {
78:   static int a[] = { 10, 15, 20, 30, 100, 5000 };
79:   for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
80:     printf("%ld ", f(a[i])); // 2813  8237158
81:   printf(       "\n17 46 86 213 2918 11134074\n");
82: }


17 46 86 213 2813 8237158
17 46 86 213 2918 11134074