题目

Problem 585: Nested square roots

新葡京娱乐场:”  那一年,他还获得“广州亚运会、亚残运会志愿者工作贡献奖”“羊城慈善先进个人慈善之星”“广东省志愿服务银奖”等多项荣誉。

Consider the term 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:



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 , 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,

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 , and , that can all three be denested into , 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 = 1, b = 2 时,就是题目中的第 1 个例子。

  2. a = 3, b = 5 时,就是题目中的第 2 个例子。

  3. Update: i = 2, c = 6, a = 2.5 也是可以的。

  4. 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 种情形的例子:




情形05中,允许 a = b 或者 a = c
情形05中,如果令 b = i2,就变为情形04,此时,不允许 a = c
情形04中,如果令 i = 1,就变为情形03,此时,要求 c > a
情形02中,如果令 a = i2,就变为情形01,此时,不要求 b > i2

不成功的解答

根据以上分析,我们有以下 C 程序:

 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

前 4 个值符合,后 2 个值不符。肯定是漏掉某些情形。