欧拉计划问题 233

Question

我决定接下来解决 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。 如果 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 的建议去做。

Answer 1

提示 1：圆的半径为 n/√2，对于整数 n 来说它永远不是整数，因此 A046080 永远不适用。

提示2：不要费力地滑动圆圈。 把它从方格纸上拿起，想一想它，定义它的正方形，以及圆周上未知的兴趣点之间的相互关系。

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

提示4：一个数可以有多少种写法来表示两个平方和？

全文中随意使用的额外提示：对称！

---

剧透警告！

---

在尝试根据上面的提示解决问题之前，请不要继续阅读

如果这些提示还不够，这里有一些缺失的步骤与上面的提示交织在一起：

提示 1.5：你将不得不改变你看待问题的方式，因为你使用的方法是基于有缺陷的前提。

提示 2.5：考虑正方形顶角之间弧线左侧的一个格点。 根据对称性，在其右侧有另一个这样的点，在其正下方还有第三个这样的点。 关于这些点之间的距离以及它们形成的三角形，你能说什么？

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

Answer 2

提示#1。你的引理#2不太正确。 你确定这是半径吗？

提示#2。答案与平方和函数 r(k, n) 密切相关。 这给出了使用 k 个不同的正方形来表示 n 的方法的数量，允许零并区分顺序。 例如，r(2, 5) 是 8，因为用 2 个正方形表示 5 有 8 种方法：

(-2)^2 + (-1)^2
(-2)^2 + 1^2
2^2    + (-1)^2
2^2    + 1^2
... (and the 4 additional expressions produced by reversing these 2 terms)

您可以看到，以原点为圆心、半径为 p 的圆有 r(2, p^2) 个格点。 例如，半径为 5 的圆有：

(-4)^2 + (-3)^2
... and 7 others like this

5^2    + 0^2
(-5)^2 + 0^2
0^2    + 5^2
0^2    + (-5)^2

总共 12 个。 什么样的数字会有 420 个圆格点？ 现在如果它们不以原点为中心怎么办？ 我会让你把它从这里拿走。

如果您想要更大的提示，我已经 rot-13'd (http://rot13.com)你应该在这里查看：

uggc://zngujbeyq.jbysenz.pbz/FpuvamryfGurberz.ugzy

Answer 3

您可以参考http://oeis.org/A046109/b046109.txt查看到 1000。我安装了 PARI/GP 并在此处使用了 PARI 脚本之一：http://oeis.org/A046109 检查更高的数字。