algorithm - 欧拉计划问题233

我已经决定接下来解决Eu​​ler项目problem 233，但是我遇到了一些主要问题!我已经进行了一些分析，并取得了相当不错的进步，但是现在我陷入了困境。这是我的工作:

引理1 :
由于圆通过4个角点，因此对于任何n至少有4个解。但是，圆周上的每个点都有7个反射点。因此，总是有8k + 4个晶格点。

引理2 :
该圆的半径为(√2)n，中心为(n/2，n/2)，因此其等式为(x-n/2)^ 2 +(y-n/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]，则解数为[0.]中的4 * product(2f [i] +1 | i。 .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的建议做。

最佳答案

提示1:圆的半径为n/√2，它永远都不是整数n的整数，因此A046080永远不适用。

提示2:不要打扰周围的圆圈。从方格纸上捡起它，然后仔细考虑一下，定义它的正方形，以及圆周上彼此之间还未知的兴趣点。

提示3:半圆内切的角度始终为90度。

提示4:一个数字可以用多少种方式写成两个平方的和？

奖金提示将在整个过程中广泛使用:对称!

警报提示!

在尝试根据以上提示进行操作之前，请先不要进一步阅读

如果这些提示还不够，那么以下是与上述提示交错的一些缺少的步骤:

提示1.5:由于您所使用的方法是基于有缺陷的前提，因此您将不得不改变看待问题的方式。

提示2.5:考虑在圆弧的左侧，在正方形的顶角之间的晶格点。通过对称，在它的右边有另一个这样的点，在下面是第三个点。关于这些点之间的距离以及它们形成的三角形，您能说什么？

提示3.5:对于任何给定的n，如何确定弧的左侧在正方形的顶角之间有多少个晶格点？

关于algorithm - 欧拉计划问题233，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/623435/