项目欧拉问题233

我决定接下来解决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).

这也为计算任何n通过A046080的解决方案的数量提供了一种简单的方法.如果4k + 1形式的n中素数的幂是f [0] ... f [m],那么解的数量是4*乘积(2f [i] +1 | i in [0 .. .M]).

这让我向后工作:4.product(2f [i] +1 | i in [0 ... m])= 420,so 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个圆格点的n的值,并且形式为2k + 1!然而,这似乎比n = 2k更难,我看不到任何方法.我也有点不确定我的答案是否正确,因为这个方法很复杂......任何人都可以确认吗？是否有一个简洁的方法,不涉及不同的处理不同的n？

我完全没有想法!

我最感兴趣的是我如何处理N = 2k + 1,因为当N = 2k时,我可以像John Feminella所说的那样做.

提示1:圆的半径为n /√2,对于整数n从不是整数,因此A046080永远不会应用.

提示2:不要打扰周围的圆圈.从方格纸上拿起它,然后想一想,定义它的方块,以及周围相对于彼此的未知的兴趣点.

提示3:内半角的角度始终为90度.

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

奖金提示在整个过程中自由使用:对称性!

SPOILER ALERT!

在您尝试从上面的提示中解决之前,请不要进一步阅读

如果这些提示不够,这里有一些与上述提示交错的缺失步骤:

提示1.5:由于您使用的方法基于有缺陷的前提,您将不得不改变查看问题的方式.

提示2.5:想想广场顶角之间弧线左侧的格点.通过对称,在它的右边有另一个这样的点,而在下面直接有第三个点.关于这些点之间的距离以及它们形成的角度,你能说些什么呢？

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