Задача Эйлера 233

Я решил заняться проблемой Project Euler 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).

Это также дает простой способ вычисления числа решений для любого n через A046080. Если степени на числах в п вида 4k + 1 равны f [0]... f [m], то число решений есть 4 * произведение (2f [i] +1 | я в [0...m]).

Это позволило мне работать в обратном направлении: 4.product(2f [i] +1 | я в [0... m]) = 420, поэтому произведение (2f [i] +1 | я в [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;
}

Нам просто нужно добавить значения n, которые имеют 420 точек решетки окружности и имеют вид 2k + 1! Однако это кажется сложнее, чем для n = 2k, и я не вижу никакого метода для него. Я также немного не уверен, правильный ли мой ответ даже для n, поскольку метод довольно запутан... Может ли кто-нибудь подтвердить это? Есть ли опрятный метод, не предусматривающий обработку разных n по-разному?

У меня все идеи!

Меня больше интересует, как я занимаюсь N = 2k + 1, так как при N = 2k я могу сделать то, что предлагает Джон Фэминелла.

Ответы

(-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)

(-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