Factorizar un entero gaussiano

23

Un número entero gaussiano es un número complejo cuyas partes reales e imaginarias son números enteros.

Los enteros gaussianos, como los enteros ordinarios, pueden representarse como un producto de números primos gaussianos, de una manera única. El desafío aquí es calcular los constituyentes primos de un entero gaussiano dado.

Entrada: un entero gaussiano, que no es igual a 0 y no es una unidad (es decir, 1, -1, i y -i no se pueden dar como entradas). Use cualquier formato sensible, por ejemplo:

  • 4-5i
  • -5 * j + 4
  • (4, -5)

Salida: una lista de enteros gaussianos, que son primos (es decir, ninguno de ellos puede representarse como un producto de dos enteros gaussianos no unitarios), y cuyo producto es igual al número de entrada. Todos los números en la lista de salida deben ser no triviales, es decir, no 1, -1, i o -i. Se puede usar cualquier formato de salida sensible; no debe ser necesariamente el mismo que el formato de entrada.

Si la lista de salida tiene más de 1 elemento, entonces son posibles varias salidas correctas. Por ejemplo, para la entrada 9, la salida puede ser [3, 3] o [-3, -3] o [3i, -3i] o [-3i, 3i].

Casos de prueba (tomados de esta tabla ; 2 líneas por caso de prueba)

2
1+i, 1-i

3i
3i

256
1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i,1+i

7+9i
1+i,2−i,3+2i

27+15i
1+i,3,7−2i

6840+585i
-1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i

Las funciones integradas para factorizar enteros gaussianos no están permitidas. Sin embargo, se permite factorizar enteros comunes mediante funciones integradas.

anatolyg
fuente
¿Debería 3iregresar como 3,io 3i?
Value Ink
3ies la respuesta correcta porque ino es primo. He actualizado el caso de prueba para hacerlo más claro.
anatolyg
¿es -3-2j, 2-1j, -1-1j una respuesta correcta para la factorización de 7 + 9j?
mdahmoune
44
Según Wolfram Alpha, 6840+585itiene la lista de factores equivocada, ya 5que no es una prima gaussiana. En cambio, vuelve -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Fuente
Value Ink
1
Para su información, 256=(1+i)**16no (1+i)**8porque 256=2**8=(2i)**8y2i=(1+i)**2
Shieru Asakoto

Respuestas:

4

Jalea , 61 55 bytes

Ḟ,Ċ1ḍP
Ḟ,ĊḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÇÐfỊÐḟ1;Ṫð,÷@\ḟ1
Ç€F$ÐL

Pruébalo en línea! (Encabezado y pie de página formatea la salida)

-6 bytes gracias a @EricTheOutgolfer

Cómo funciona

Ḟ,Ċ1ḍP  - helper function: determines if a complex number is Gaussian
Ḟ,Ċ       - real, complex components
   1ḍ     - set each to if 1 divides them
     P    - all

Ḟ,ĊḤp/-,1p`¤×€×1,ıFs2S€⁸÷ÇÐfỊÐḟ1;Ṫð,÷@\ḟ1 - helper: outputs a factor pair of the input
Ḟ,ĊḤp/                   - creates a list of possible factors a+bi, a,b>=0
      -,1p`¤×€           - extend to the other three quadrants 
              ×1,ıFs2S€  - convert to  actual complex numbers 
⁸÷                       - get quotient with input complex number
  ÇÐf                    - keep only Gaussian numbers (using helper function)
     ỊÐḟ                 - remove units (i,-i,1,-1)
        1;               - append a 1 to deal with primes having no non-unit factors
          Ṫð,÷@\         - convert to a factor pair
                ḟ1       - remove 1s
Ç€F$ÐL
Ç€      - factor each number
   $    - and
  F     - flatten the list
    ÐL  - until factoring each number and flattening does not change the list
fireflame241
fuente
cuando esto dice "mantener solo Gaussian", ¿significa "mantener solo Primes"?
Don brillante
@donbright no, se refiere a mantener solo esos números complejos con componentes enteros reales y complejos
fireflame241
@ fireflame241 oh ya veo ahora! muchas gracias
don brillante
5

Rubí , 258 256 249 246 + 8 = 264 257 254 bytes

Usa la -rprimebandera.

Caray, que desastre.

Utiliza este algoritmo de stackoverflow.

->c{m=->x,y{x-y*eval("%d+%di"%(x/y).rect)};a=c.abs2.prime_division.flat_map{|b,e|b%4<2?(1..e).map{k=(2..d=b).find{|n|n**(~-b/2)%b==b-1}**(~-b/4)%b+1i;d,k=k,m[d,k]while k!=0;c/=d=m[c,d]==0?d:d.conj;d}:(c/=b<3?(b=1+1i)**e:b**e/=2;[b]*e)};a[0]*=c;a}

Pruébalo en línea!

Tinta de valor
fuente
5

Python 2 , 250 239 223 215 bytes

e,i,w=complex,int,abs
def f(*Z):
 if Z:
	z=Z[0];q=i(w(z));Q=4*q*q
	while Q>0:
 	 a=Q/q-q;b=Q%q-q;x=e(a,b)
 	 if w(x)>1:
		y=z/x
		if w(y)>1 and y==e(i(y.real),i(y.imag)):f(x,y);z=Q=0
 	 Q-=1
	if z:print z
	f(*Z[1:])

Pruébalo en línea!

  • -11 bytes cuando se utilizan argumentos de funciones múltiples
  • -2² * ² bytes cuando se usa una variable para analizar parejas (a,b)
  • -2³ bytes al mezclar pestañas y espacios: gracias a los ovs

Algunas explicaciones descomponen recursivamente un complejo en dos complejos hasta que no sea posible la descomposición ...

mdahmoune
fuente
Bueno, se agota el tiempo de espera en TIO en entradas más grandes, pero es más corto que mi respuesta de Ruby ... por ahora . Además, def f(Z,s=[])debería ahorrarte un personaje
Value Ink
@ValueInk sí, es más lento que su solución de rubí
mdahmoune
2
Patrón interesante con la sangría ...
Erik the Outgolfer
@ValueInk Los argumentos de funciones múltiples ahorran más bytes :)
mdahmoune
1
Usted puede reducir su cuenta de bytes por mezclar las fichas y espacios
ovs
3

Óxido - 212 bytes

use num::complex::Complex as C;fn f(a:&mut Vec<C<i64>>){for _ in 0..2{for x in -999..0{for y in 1..999{for i in 0..a.len(){let b=C::new(x,y);if(a[i]%b).norm_sqr()==0&&(a[i]/b).norm_sqr()>1{a[i]/=b;a.push(b)}}}}}}

No estoy 100% seguro de si esto funciona 100% correcto, pero parece ser correcto para una amplia gama de pruebas. Esto no es más pequeño que Jelly, pero al menos es más pequeño que los idiomas interpretados (hasta ahora). También parece ser más rápido y puede funcionar a través de entradas de mil millones de magnitud en menos de un segundo. Por ejemplo, 1234567890 + 3141592650i factores como (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (haga clic aquí para probar Wolfram Alpha)

Esto comenzó como la misma idea que la factorización ingenua de enteros, para pasar por cada número debajo del entero en cuestión, ver si se divide, repetir hasta que esté hecho. Luego, inspirado por otras respuestas, se transformó ... factoriza repetidamente elementos en un vector. Hace esto un buen número de veces, pero no 'hasta' nada. El número de iteraciones se ha elegido para cubrir una buena porción de entradas razonables.

Todavía usa "(a mod b) == 0" para probar si un número entero divide a otro (para los gaussianos, usamos el módulo gaussiano Rust incorporado, y consideramos que "0" es la norma == 0), sin embargo, la verificación de 'norma ( a / b)! = 1 'evita dividir "demasiado", básicamente permitiendo que el vector resultante se llene solo con números primos, pero sin llevar a la unidad ningún elemento del vector (0-i, 0 + i, -1 + 0i, 1 + 0i) (que está prohibido por la pregunta).

Los límites for-loop se encontraron a través del experimento. y va de 1 en adelante para evitar el pánico de división por cero, y x puede ir de -999 a 0 gracias a la duplicación de gaussianos sobre los cuadrantes (¿creo?). En cuanto a las limitaciones, la pregunta original no indicaba un rango válido de entrada / salida, por lo que se supone un "tamaño de entrada razonable" ... (Editar ... sin embargo, no estoy exactamente seguro de cómo calcular en qué número esto comienzan a "fallar", me imagino que hay enteros gaussianos que no son divisibles por nada por debajo de 999 pero que son sorprendentemente pequeños para mí)

Prueba la versión un tanto descuidada en play.rust-lang.org

don brillante
fuente
3

Perl 6 , 141 bytes

Gracias a Jo King por -17 bytes

sub f($_){{$!=0+|sqrt .abs²-$^a²;{($!=$_/my \w=$^b+$a*i)==$!.floor&&.abs>w.abs>1>return f w&$!}for -$!..$!}for ^.abs;.say}

Pruébalo en línea!

bb94
fuente
¿como funciona esto? ¿Es el piso un módulo personalizado?
Don brillante
1
@donbright La floorparte está verificando si $_/w(es decir, el factor actual dividido por un número) es un número entero
Jo King
2

Pyth , 54 51 45 42 36 bytes

 .W>H1cZ
h+.aDf!%cZT1>#1.jM^s_BM.aZ2

Pruébalo en línea!

Acepta la entrada en el formulario 1+2j: los números puramente reales o imaginarios pueden omitir el otro componente (por ejemplo 9, 2j). La salida es una lista separada por una nueva línea de números complejos, en la forma(1+2j) , con números puramente imaginarios que omiten la parte real.

Esto utiliza la división de senderos simple, generando todos los enteros gaussianos con una magnitud mayor que 1 y menor que el valor actual, más el valor en sí. Estos se filtran para mantener aquellos que son un factor del valor, y el más pequeño por magnitud se elige como el siguiente factor primo. Esta es la salida, y el valor se divide por ella para producir el valor para la próxima iteración.

Además, Pyth vence a Jelly 😲 (aunque no espero que dure)

 .W>H1cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2ZQ   Implicit: Q=eval(input())
                                         Newline replaced with ¶, trailing ZQ inferred
 .W                                  Q   While <condition>, execute <inner>, with starting value Q
   >H1                                   Condition function, input H
   >H1                                     Is magnitude of H > 1?
                                           This ensures loop continues until H is a unit, i.e. 1, -1, j, or -j)
      cZ¶h+.aDf!%cZT1>#1.jM^s_BM.aZ2Z    Inner function, input Z
                                .aZ        Take magnitude of Z

                             _BM           Pair each number in 0-indexed range with its negation
                            s              Flatten
                           ^       2       Cartesian product of the above with itself
                        .jM                Convert each pair to a complex number
                      #                    Filter the above to keep those element where...
                     > 1                   ... the magnitude is greater than 1 (removes units)
              f                            Filter the above, as T, to keep where:
                 cZT                         Divide Z by T
                %   1                        Mod real and imaginary parts by 1 separately
                                             If result of division is a gaussian integer, the mod will give (0+0j)
               !                             Logical NOT - maps (0+0j) to true, all else to false
                                           Result of filter are those gaussian integers which evenly divide Z
           .aD                             Sort the above by their magnitudes
          +                         Z      Append Z - if Z is ±1±1j, the filtered list will be empty
         h                                 Take first element, i.e. smallest factor
        ¶                                  Print with a newline
      cZ                                   Divide Z by that factor - this is new input for next iteration
                                         Output of the while loop is always 1 (or -1, j, or -j) - leading space suppesses output
Sok
fuente
esto es muy interesante, pero parece que el tiempo de espera en 6840 + 585j
don brillante
@donbright Lo hace en TIO, ya que tiene un límite de procesamiento de 60 s. Funcionará con más tiempo, por lo que si lo está ejecutando localmente debería funcionar sin problemas.
Sok