Proyecto Euler Problema 233
https://stackoverflow.com/questions/623435
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He decidido abordar el Proyecto Euler problema 233 a continuación, pero Estoy teniendo algunos problemas importantes! He hecho algunos análisis y he hecho algunos progresos bastante buenos, pero ahora me he quedado atascado. Aquí está mi trabajo:
Lemma 1 : Dado que el círculo atraviesa los 4 puntos de la esquina, hay al menos 4 soluciones para cualquier n. Pero para cada punto de la circunferencia hay otros 7 encontrados con reflexión. Por lo tanto, siempre hay 8k + 4 puntos de celosía.
Lemma 2 : El círculo tiene radio (& # 8730; 2) n y centro (n / 2, n / 2), por lo que su ecuación es (xn / 2) ^ 2 + (yn / 2) ^ 2 = [n / & # 8730; 2] ^ 2. Esto se reduce a x ^ 2 + y ^ 2 = n (x + y).
Lemma 3 : Si se escribe una solución de x ^ 2 + y ^ 2 = n (x + y) (x, y, z), entonces otra solución es (kx, ky, kz). La prueba de ello es:
(x+y)n = x^2+y^2
(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn
Esto fue todo lo que hice con esa línea de pensamiento: no pude ver a dónde ir, pero está incluido porque puede ser útil.
Mi siguiente pensamiento fue mover el centro del círculo. Habrá el mismo número de soluciones moviéndolo en cualquier dimensión a un entero entero. Entonces cuando n / 2 es un número entero, entonces n = 2k, x ^ 2 + y ^ 2 = 2 * k ^ 2. Y también resulta que hay tantas soluciones para esta ecuación como para la ecuación x ^ 2 + y ^ 2 = k ^ 2 (vea Sloane A046109 ).
Esto también proporciona un método fácil para calcular el número de soluciones para cualquier n a través de A046080 . Si las potencias en los números primos en n de la forma 4k + 1 son f [0] ... f [m], entonces el número de soluciones es 4 * producto (2f [i] +1 | i en [0 .. .m]).
Esto me permitió trabajar hacia atrás: 4.product (2f [i] +1 | i en [0 ... m]) = 420, así que el producto (2f [i] +1 | i en [0 .. .m]) = 105 = 3 * 5 * 7. Pude encontrar este programa que creo que encuentra la suma de todos n, en la forma 2k y menos de 10 ^ 11, que tienen 420 puntos de celosía de círculo. La respuesta (¡espero!) Es 257199853438240692.
Aquí está el programa 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;
}
¡Solo necesitamos agregar los valores de n que tienen 420 puntos de celosía de círculo y están en la forma 2k + 1! Sin embargo, eso parece más difícil que para n = 2k y no puedo ver ningún método para ello. Tampoco estoy seguro si mi respuesta para incluso n es correcta ya que el método es bastante complicado. ¿Alguien puede confirmarlo? ¿Existe un método claro sin involucrar el tratamiento de n diferente?
¡Me he quedado sin ideas!
Estoy más interesado en cómo trato con N = 2k + 1 ya que cuando N = 2k puedo hacer lo que sugiere John Feminella.
Solución
Sugerencia 1: el círculo tiene un radio n / v2, que nunca es un número entero para el entero n, por lo que A046080 nunca se aplica.
Sugerencia 2: No te molestes en deslizar el círculo alrededor. Levántelo del papel cuadriculado y solo piénselo, el cuadrado que lo define y los puntos de interés aún desconocidos sobre la circunferencia entre sí.
Sugerencia 3: el ángulo inscrito en un semicírculo es siempre de 90 grados.
Sugerencia 4: ¿De cuántas maneras se puede escribir un número como la suma de dos cuadrados?
Sugerencia de bonificación para ser usada generosamente en: simetría!
¡ALERTA DE SPOILER!
No lea más hasta que intente resolverlo a partir de las sugerencias anteriores
Si esas sugerencias no son suficientes, estos son algunos de los pasos que faltan para intercalar con las sugerencias anteriores:
Sugerencia 1.5: tendrá que cambiar su forma de ver el problema, ya que el enfoque que estaba utilizando se basa en una premisa defectuosa.
Sugerencia 2.5: Piense en un punto de celosía en el lado izquierdo del arco entre las esquinas superiores del cuadrado. Por simetría hay otro tal punto directamente a la derecha de él y un tercero directamente debajo. ¿Qué puede decir sobre la distancia entre estos puntos y sobre el triángulo que forman?
Sugerencia 3.5: ¿Cómo puedes determinar cuántos puntos de celosía hay en el lado izquierdo del arco entre las esquinas superiores del cuadrado para cualquier n dada?
Otros consejos
Sugerencia # 1. Tu lema # 2 no está del todo bien. ¿Estás seguro de que ese es el radio?
Sugerencia # 2. La respuesta está estrechamente relacionada con la función de la suma de los cuadrados, r (k, n). Esto da el número de formas para representar n usando k cuadrados diferentes, permitiendo ceros y distinguiendo entre orden. Por ejemplo, r (2, 5) es 8, porque hay 8 formas de representar 5 usando 2 cuadrados:
(-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)
Puede ver que un círculo de radio p centrado en el origen tiene r (2, p ^ 2) puntos de red. Por ejemplo, un círculo con radio 5 tiene:
(-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
para un total de 12. ¿Qué tipo de números tendrían 420 puntos de celosía de círculo? ¿Y ahora si no estuvieran centrados en el origen? Te dejaré tomarlo desde aquí.
Si desea una pista mucho más grande, he rot-13'd ( http://rot13.com ) algo que deberías revisar aquí:
uggc: //zngujbeyq.jbysenz.pbz/FpuvamryfGurberz.ugzy
Puede consultar http://oeis.org/A046109/b046109.txt para verificar hasta 1000. Instalé PARI / GP y usé uno de los scripts PARI aquí: http://oeis.org/ A046109 para verificar los números más altos.
