Projeto Euler problema 233
https://stackoverflow.com/questions/623435
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu decidi enfrentar Projeto Euler problema 233 seguinte, mas eu estou tendo alguns problemas importantes! Já fiz algumas análises e ter feito algum progresso muito bom, mas eu ficar preso agora. Aqui é o meu trabalho:
Lema 1 : Uma vez que o círculo passa através dos 4 pontos de canto, existem, pelo menos, 4 soluções para qualquer n. Mas para cada ponto da circunferência há 7 outros encontrados com reflexão. Portanto, há sempre 8k + 4 pontos de rede.
Lema 2 : O círculo tem um raio (v2) n e centro (n / 2, n / 2), de modo a equação é (X-N / 2) ^ 2 + (y-N / 2) ^ 2 = [n / v2] ^ 2. Isto reduz para baixo a x ^ 2 + y = n ^ 2 (x + y).
Lema 3 : Se uma solução de 2 ^ x + y = n ^ 2 (x + y) é gravada (x, y, z), em seguida, uma outra solução é (kx, ky, kz). A prova disso é:
(x+y)n = x^2+y^2
(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn
Este foi, tanto quanto eu fiz com essa linha de pensamento - eu não podia ver para onde ir de lá, mas ele está incluído, pois bem pode ser útil
.Meu próximo pensamento foi para mover o centro do círculo. Haverá o mesmo número de soluções móveis que em qualquer dimensão um número inteiro. Assim, quando n / 2 é inteiro, de modo que n = 2k, x + y ^ 2 ^ 2 = 2 * k ^ 2. E também acontece que existem apenas como muitas soluções para esta equação, pois há a equação x ^ 2 + y ^ 2 = k ^ 2 (ver Sloane A046109 ).
Isso também dá um método fácil para calcular o número de soluções para qualquer n via A046080 . Se as potências sobre os números primos em N da forma 4k + 1 são f [0] ... f [m], então o número de soluções é 4 * produto (2f [i] 1 | i no [0 .. .m]).
Isso me permitiu trás de trabalho: 4.Product (2f [i] +1 | i em [0 ... m]) = 420, assim produto (2f [i] +1 | i em [0 .. .m]) = 105 = 3 * 5 * 7. Eu era capaz de chegar a este programa que eu acho que localiza a soma de todos os n, na forma 2k e menos de 10 ^ 11, que tem 420 pontos círculo de treliça. A resposta (espero!) É 257199853438240692.
Aqui está o 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;
}
Nós só precisa adicionar os valores de n que têm 420 pontos círculo de treliça e estão na forma 2k + 1! No entanto, isso parece mais difícil do que para n = 2k e eu não posso ver qualquer método para ele. Eu também sou um pouco certeza se a minha resposta até mesmo para n é correta, já que o método é bastante complicado ... Alguém pode confirmar isso? Existe um método limpo, sem envolver o tratamento diferente n diferente?
Eu estou fora das idéias!
Estou mais interessada em como eu lido com N = 2k + 1 desde quando N = 2k eu posso fazer como John Feminella sugere.
Solução
Sugestão 1: O círculo tem um raio n / v2, que nunca é um número inteiro para o inteiro n, de modo que nunca a aplica A046080
.Dica 2: Não se preocupe em correr o círculo ao redor. Pegá-lo fora do papel de gráfico e apenas pensar sobre isso, a praça que a define, e os pontos ainda desconhecidos de interesse na circunferência em relação ao outro.
Dica 3:. O ângulo inscrito num semicírculo é sempre 90 graus
Dica 4: Quantas maneiras pode um número ser escrito como a soma de dois quadrados
dica bônus para ser usado livremente em todo: simetria
ALERTA DE SPOILER!
Não leia mais até você tentar trabalhá-lo para fora das dicas acima
Se essas dicas não são suficientes, aqui estão alguns dos passos que faltam para intercalar com as dicas acima:
Dica 1.5:. Você vai ter que mudar sua maneira de olhar para o problema, já que a abordagem que você estava usando é baseado em uma premissa defeituosa
Dica de 2,5: Pense em um ponto da rede no lado esquerdo do arco entre os principais cantos do quadrado. Por simetria há um outro ponto tal diretamente à direita dele e um terceiro logo abaixo. O que você pode dizer sobre a distância entre estes pontos e sobre a trangle eles formam?
Dica 3.5:? Como você pode determinar quantos treliça pontos existem no lado esquerdo do arco entre os principais cantos do quadrado para qualquer n
Outras dicas
Dica # 1. O seu lema # 2 não é muito justo. Tem certeza que é o raio?
(-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)
Você pode ver que um círculo de raio p centrado na origem tem r (2, p ^ 2) pontos de rede. Por exemplo, um círculo com raio de 5 tem:
(-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 um total de 12. Que tipos de números teria 420 pontos círculo de rede? Agora, o que se não fossem centrado na origem? Eu vou deixar você levá-lo a partir daqui.
Se você quer uma dica muito, muito maior, eu rot-13'd ( http://rot13.com ) algo que você deve verificar se aqui:
uggc: //zngujbeyq.jbysenz.pbz/FpuvamryfGurberz.ugzy
Você pode consultar a http://oeis.org/A046109/b046109.txt para verificar até 1000. Eu instalei PARI / GP e usado um dos scripts PARI aqui: http://oeis.org/ A046109 para verificar os números mais elevados.
