Я решил заняться проблемой 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 (см. Слоан A046109 ).
Это также дает простой метод для вычисления числа решений для любого n через A046080 . Если степени простых чисел в n вида 4k + 1 равны f [0] ... f [m], то число решений равно 4 * произведению (2f [i] +1 | i в [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;
}
Нам просто нужно добавить значения n, которые имеют 420 точек решетки окружности и имеют вид 2k + 1! Тем не менее, это кажется сложнее, чем для n = 2k, и я не вижу никакого способа для этого. Я также немного не уверен, правильный ли мой ответ для четного n, поскольку метод довольно запутанный ... Кто-нибудь может это подтвердить? Есть ли аккуратный метод, не требующий различного отношения к n?
У меня нет идей!
Меня больше всего интересует, как я справляюсь с N = 2k + 1, поскольку, когда N = 2k, я могу делать то, что предлагает Джон Феминелла.