Я решил заняться Project Euler проблемой 233 следующей, но у меня возникли некоторые серьезные проблемы! Я провел некоторый анализ и добился неплохого прогресса, но теперь я застрял. Вот моя работа:
Лемма 1: поскольку окружность проходит через 4 угловые точки, существует по крайней мере 4 решения для любого n. Но на каждую точку окружности с отражением найдено 7 других. Следовательно, всегда имеется 8k+4 узлов решетки.
Лемма 2: окружность имеет радиус (√2)n и центр (n/2, n/2), поэтому ее уравнение (xn/2)^2 + (yn/2)^2 = [н/√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. Если степени простых чисел в n вида 4k+1 равны f[0]...f[m], то число решений равно 4*product(2f[i]+1 | i in [0.. .м]).
Это позволило мне работать в обратном порядке: 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.
Вот программа на Си:
#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, я могу поступить так, как предлагает Джон Феминелла.
