项目欧拉问题233欧拉、项目、问题

2023-09-11 03:44:32 作者：薄荷小仙女

我已经决定，以解决项目欧拉问题233 旁边，但我有一些主要的问题！我做了一些分析，并取得了一些相当不错的进展，但我已经成为现在卡住。这是我的工作：

I've decided to tackle Project Euler problem 233 next but I'm having some major problems! I've done some analysis and have made some quite nice progress but I've become stuck now. Here's my working:

引理1 ：由于圆穿过4角点至少有4解任意n。但是，对于上围的每个点有7人与反思中。因此总有8K + 4格子点

Lemma 1: Since the circle goes through the 4 corner points there are at least 4 solutions for any n. But for each point on the circumference there are 7 others found with reflection. Therefore there are always 8k+4 lattice points.

引理2 ：圆具有半径（√2）n和中心（N / 2，N / 2），所以它是方程（XN / 2）^ 2 +（炔/ 2）^ 2 = [N /√2] ^ 2。这将减少到X ^ 2 + Y ^ 2 = N（X + Y）。

Lemma 2: The circle has radius (√2)n and center (n/2, n/2) so its equation is (x-n/2)^2 + (y-n/2)^2 = [n/√2]^2. This reduces down to x^2+y^2 = n(x+y).

引理3 ：如果一个解x ^ 2 + Y ^ 2 = N（X + Y）被写入（X，Y，Z），那么另一种解决方案是（KX，KY，KZ）。那证据是：

Lemma 3: If a solution of x^2+y^2 = n(x+y) is written (x, y, z) then another solution is (kx, ky, kz). The proof of that is:

(x+y)n = x^2+y^2

(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn

这是像我那样与思路 - 我看不到任何地方，从那里走，但它包括在内，因为它也可能是有用的。

This was as much as I did with that line of thought - I couldn't see anywhere to go from there but it's included because it well may be useful.

我的下一个想法是移动的圆心。会有解决移动它在任何尺寸的所有整数的数相同。所以，当n / 2是整数，所以N = 2K，X ^ 2 + Y ^ 2 = 2 * K ^ 2。而且它也变成了有同样多的解决方案，这个方程，因为有对方程x ^ 2 + Y ^ 2 = K ^ 2（见斯隆的 A046109 ）。

My next thought was to move the center of the circle. There will be the same number of solutions moving it in any dimension a whole integer. So when n/2 is integer, so n=2k, x^2+y^2 = 2*k^2. And it also turns out that there are just as many solutions to this equation as there are to the equation x^2+y^2=k^2 (see Sloane A046109).

这也给出了一个简单的方法来计算解决方案的数量通过 A046080 的任意n。如果在正的形式4K + 1，对素数的权力是f [0] ... F [米]，则解的个数是4 *产物（2F [I] 1 | i的[0 .. .M]）。

This also gives an easy method for computing the number of solutions for any n via A046080. If the powers on the primes in n of the form 4k+1 are f[0]...f[m], then the number of solutions is 4*product(2f[i]+1 | i in [0...m]).

这让我向后工作：4。产品（2F [I] +1 |我在[0 ... M）= 420，所以产品（2F [I] +1 |在我[0 .. .M）= 105 = 3 * 5 * 7。我能想出这个计划，我想找到所有n的总和，其形式2K不到10 ^ 11，其中有420圆格点。答案（我希望如此！）是257199853438240692。

This allowed me to work backwards: 4.product(2f[i]+1 | i in [0...m]) = 420, so product(2f[i]+1 | i in [0...m]) = 105 = 3*5*7. I was able to come up with this program which I think finds the sum of all n, in the form 2k and less than 10^11, which have 420 circle lattice points. The answer (I hope!) is 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;
}

我们只需要添加n的有420圆阵点，并在形式2K + 1的值！然而，这似乎比N = 2K更难，我看不到任何方法吧。我也有点不确定我的偶数n的答案是否正确，因为该方法是相当令人费解......任何人都可以证实。是否有一个整洁的方法，而不涉及区别对待不同的N +

We just need to add on the values of n that have 420 circle lattice points and are in the form 2k+1! However, that seems harder than for n=2k and I can't see any method for it. I'm also a little unsure whether my answer for even n is correct since the method is quite convoluted... Can anyone confirm it? Is there a neat method without involving treating different n differently?

我所有的想法！

我最感兴趣的是我怎么收拾N = 2K + 1，因为当N = 2K我能做到像约翰Feminella建议。

I'm mostly interested in how I deal with N=2k+1 since when N=2k I can do as John Feminella suggests.

项目欧拉问题233欧拉、项目、问题

推荐答案