Nos dan un número n. ¿Cómo encontramos eficientemente los números x e y como x ^ 2 + y ^ 2 = n?

Answer 1

Si tiene un algoritmo de factorización rápido (más rápido que [math] O (\ sqrt {n}) [/ math]), puede utilizar algunas matemáticas para obtener una respuesta más rápida. Usando algunas propiedades encontradas por Fermat, sabemos que cada primo [math] p \ equiv 1 [/ math] mod 4 puede expresarse como la suma de dos cuadrados exactamente de una manera. La solución particular se puede resolver en tiempo logarítmico (ver página en www.emis.de).

Luego, para resolver cualquier número entero arbitrario, solo tenemos que descomponerlo en factores primos y luego fusionar soluciones usando la identidad [matemáticas] (a ^ 2 + b ^ 2) (c ^ 2 + d ^ 2) = (ac + bd) ^ 2 + (ad-bc) ^ 2 [/ matemáticas]. Por supuesto, también necesitamos verificar el poder de 2 y los poderes de los primos de la forma [math] p \ equiv 3 [/ math] mod 4. Si alguno de esos poderes es impar, no hay soluciones. Por ejemplo, si la factorización prima tiene una potencia impar de 2, es claramente insoluble (para x <y).

Los factores extra constantes y la complejidad de este enfoque son probablemente excesivos para la mayoría de los propósitos prácticos, pero no obstante es interesante.

Fuentes: Triples pitagóricos, enumerando formas de descomponer un número entero en la suma de dos cuadrados

Answer 2

Esto representa la ecuación de un círculo centrado en el origen. Puede haber infinitos números (números reales) que satisfagan esta ecuación. Pero, si está pidiendo números enteros, encuentre la raíz cuadrada de ‘n’ que le dará el radio del círculo. Ahora, el valor de ‘x’ e ‘y’ ciertamente se encuentra entre [ -sqrt (n), + sqrt (n)] .
Ahora, podemos encontrar los puntos en el primer cuadrante (de modo que sean enteros) y multiplicarlo por 4 dará todos los números que satisfacen esta ecuación. Esto se puede hacer fácilmente. Este ejemplo lo dejará claro:
Asumir:
[matemáticas] x ^ 2 + y ^ 2 = 25 [/ matemáticas]
entonces los puntos se encuentran entre -5 y +5.
tomar i = 0, j = 5
[matemáticas] i ^ 2 + j ^ 2 = 25 [/ matemáticas]
Este punto se encuentra en el círculo, aumenta el recuento a ‘1’. aumentar ‘i’, disminuir ‘j’.
i = 1, j = 4
[matemáticas] i ^ 2 + j ^ 2 = 17 [/ matemáticas]
Este punto se encuentra dentro del círculo, aumentar ‘i’, ‘j’ sigue siendo el mismo.
i = 2, j = 4
[matemáticas] i ^ 2 + j ^ 2 = 20 [/ matemáticas]
Este punto se encuentra dentro del círculo, aumentar ‘i’, ‘j’ sigue siendo el mismo.
i = 3, j = 4
[matemáticas] i ^ 2 + j ^ 2 = 25 [/ matemáticas]
Este punto se encuentra en el círculo, aumenta ‘i’, aumenta ‘j’, aumenta el conteo a 2.
i = 4, j = 3, pero adivina qué, esto dará resultados que ya están calculados. Entonces, rompa el ciclo (cuando i> j).

Como cuenta = 2, multiplíquelo por 4.
cuenta se convierte en 8, por lo que hay 8 puntos enteros en el círculo. ‘2’ en cada cuadrante.
(5,0)
(-5,0)
(0, -5)
(0,5)
(3,4)
(3, -4)
(-3,4)
(-3, -4)

Esto tomará [math] O (sqrt (n)) [/ math], no sé si se puede hacer menos que esta vez. En caso afirmativo, proporcione la respuesta y, si hay algún error, comente.

Answer 3

Hacer algunas matemáticas antes de escribir el código a veces puede disminuir el tiempo y la complejidad, además de la fuerza bruta. Primero debemos suponer que x e y son enteros; de lo contrario, la pregunta es trivial. Luego, debe determinar si hay alguna solución o no. Deberías factorizar n. Si n tiene un factor primo p, tal que [matemática] p \ equiv 3 \ bmod 4 [/ matemática], entonces su exponente debe ser par para que n sea una suma de dos cuadrados. Entonces, si su exponente es impar, ni siquiera se moleste. Si hay una [matemática] p \ equiv 3 \ bmod 4 [/ matemática] y su exponente es par, tal vez [matemática] {p ^ {2k}} [/ matemática] entonces también tiene los otros factores recolectados, digamos en una variable X.

Entonces [matemáticas] n = {p ^ {2k}} X. [/ Matemáticas]. Tenga en cuenta que [math] X

Si hay otros números primos, como [math] q \ equiv 1 \ bmod 4 [/ math], no importa sus exponentes, simplemente continúe. Su tarea será escribir q como una suma de dos cuadrados. Antes de entrar en cómo hacer eso, supongamos que encontramos dos primos, q y r y hemos determinado que [matemáticas] q = {a ^ 2} + {b ^ 2} [/ matemáticas] y [matemáticas] r = { c ^ 2} + {d ^ 2} [/ math], entonces el siguiente truco te dará qr como una suma de dos cuadrados:

[matemáticas] \ left ({{a ^ 2} + {b ^ 2}} \ right) \ left ({{c ^ 2} + {d ^ 2}} \ right) = {\ left ({ac + bd } \ right) ^ 2} + {\ left ({ad – bc} \ right) ^ 2} [/ math]

Escribir q como la suma de dos cuadrados es una tarea de programación fácil ya que q debería ser mucho más pequeño que n