我决定接下来解决 Project Euler问题 233，但我遇到了一些重大问题！我已经做了一些分析并取得了一些相当不错的进展，但我现在陷入了困境。这是我的工作：
引理 1：由于圆穿过 4 个角点，因此任何 n 至少有 4 个解。但是对于圆周上的每个点，通过反射发现了另外 7 个点。因此总是有 8k+4 个格点。
引理 2：圆的半径为 (√2)n，圆心为 (n/2, n/2)，因此其方程为 (xn/2)^2 + (yn/2)^2 = [n/√2]^ 2. 这减少到 x^2+y^2 = n(x+y)。
引理 3：如果 x^2+y^2 = n(x+y) 的解写成 (x, y, z)，则另一个解是 (kx, ky, kz)。证明是：
(x+y)n = x^2+y^2
(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn
这与我对这种思路所做的一样多 - 我看不到从那里去的任何地方，但它被包括在内，因为它可能很有用。
我的下一个想法是移动圆心。将有相同数量的解决方案在任何维度上移动一个整数。所以当n/2为整数时，所以n=2k，x^2+y^2 = 2*k^2。而且事实证明，这个方程的解与方程 x^2+y^2=k^2 的解一样多（参见 Sloane A046109）。
这也提供了一种通过A046080计算任何 n 的解决方案数量的简单方法。如果 4k+1 形式的 n 中素数的幂是 f[0]...f[m]，则解的数量是 4*product(2f[i]+1 | i in [0.. .m]）。
这让我可以向后工作： 4.product(2f[i]+1 | i in [0...m]) = 420, 所以 product(2f[i]+1 | i in [0...m] ) = 105 = 3*5*7。我能够想出这个程序，我认为它可以找到所有 n 的总和，形式为 2k 且小于 10^11，它有 420 个圆格点。答案（我希望！）是 257199853438240692。
这是C程序：
#include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "string.h"
#define lim 1000000000L
char prime[lim];
long primes[50000000];
long len = 0;
int main(void)
{
long i, j;
for(i = 0; i < lim; i++)
{
prime[i] = 1;
}
for(i = 2; i < lim; i++)
{
if(prime[i])
{
for(j = 2*i; j < lim; j += i) prime[j] = 0;
if((i-1)%4 == 0)
{
prime[i] = 2;
//printf("%li\n", i);
primes[len++] = i;
}
}
if(i < 1000 || (i < 10000 && i%1000 == 0) || i%10000 == 0) printf("%li, %li\n", i, len);
}
printf("primes!\n");
long a, b, c, v, total = 0, k;
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(c = 0; c < len; c++)
{
if(c == a) continue;
if(c == b) continue;
v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[c];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
}
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
for(a = 0; a < len; a++)
{
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
if(v > 50000000000L) break;
for(b = 0; b < len; b++)
{
if(b == a) continue;
v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
if(v > 50000000000L) break;
for(k = 1; k*v <= 50000000000L; k++)
{
if(prime[k] == 2) continue;
total += k*v;
}
}
}
printf("%li\n", 2*total);
return 0;
}
我们只需要将具有 420 个圆格点且形式为 2k+1 的 n 的值相加！但是，这似乎比 n=2k 更难，而且我看不到任何方法。我也有点不确定我对偶数 n 的回答是否正确，因为该方法非常复杂......有人可以确认吗？有没有一种简洁的方法而不涉及不同地对待不同的 n？
我完全没主意了！
我最感兴趣的是我如何处理 N=2k+1，因为当 N=2k 时，我可以按照 John Feminella 的建议进行操作。