Fatorar um número inteiro gaussiano

23

Um número inteiro gaussiano é um número complexo cujas partes reais e imaginárias são números inteiros.

Inteiros gaussianos, como inteiros comuns, podem ser representados como um produto de números primos gaussianos, de uma maneira única. O desafio aqui é calcular os constituintes principais de um dado inteiro gaussiano.

Entrada: um número inteiro gaussiano, que não é igual a 0 e não é uma unidade (ou seja, 1, -1, iei não podem ser dados como entradas). Use qualquer formato sensível, por exemplo:

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

Saída: uma lista de números inteiros gaussianos, que são primos (ou seja, nenhum deles pode ser representado como um produto de dois números inteiros gaussianos não unitários) e cujo produto é igual ao número de entrada. Todos os números na lista de saída devem ser não triviais, ou seja, não 1, -1, i ou -i. Qualquer formato de saída sensível pode ser usado; não deve necessariamente ser o mesmo que o formato de entrada.

Se a lista de saída tiver mais de 1 elemento, serão possíveis várias saídas corretas. Por exemplo, para a entrada 9, a saída pode ser [3, 3] ou [-3, -3] ou [3i, -3i] ou [-3i, 3i].

Casos de teste (extraídos desta tabela ; 2 linhas por caso de teste)

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

Funções internas para fatorar números inteiros gaussianos não são permitidas. No entanto, é permitido levar em consideração números inteiros comuns por funções internas.

anatolyg
fonte
Deve 3iretornar como 3,iou 3i?
Value Ink
3ié a resposta correta porque inão é primo. Atualizei o caso de teste para torná-lo mais claro.
21817 Anatolyg
3-2j, 2-1j, -1-1j é a resposta correta para a fatoração de 7 + 9j?
Mdahmoune
4
Segundo Wolfram Alpha, 6840+585item a lista errada de fatores, pois 5não é um primo gaussiano. Em vez disso, ele retorna -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Fonte
Value Ink
1
FYI, 256=(1+i)**16não (1+i)**8porque 256=2**8=(2i)**8e2i=(1+i)**2
Shieru Asakoto 23/02

Respostas:

4

Geléia , 61 55 bytes

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

Experimente online! (Cabeçalho e rodapé formata a saída)

-6 bytes graças a @EricTheOutgolfer

Como 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
fonte
quando diz "mantenha apenas gaussiano", significa "mantenha apenas primos"?
don bright
@donbright não, ele se refere a manter apenas os números complexos com bens inteiro e componentes complexos
fireflame241
@ fireflame241 oh eu vejo agora! muito obrigado
don brilhante
5

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

Usa a -rprimebandeira.

Nossa, que bagunça.

Usa esse algoritmo do 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}

Experimente online!

Value Ink
fonte
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:])

Experimente online!

  • -11 bytes ao usar argumentos de múltiplas funções
  • -2² * ² bytes ao usar uma variável para analisar casais (a,b)
  • -2³ bytes ao misturar guias e espaços: graças ao ovs

Alguma explicação decompõe recursivamente um complexo em dois complexos até que nenhuma decomposição seja possível ...

mdahmoune
fonte
Bem, o tempo limite é excedido no TIO em entradas maiores, mas é mais curto do que minha resposta do Ruby ... por enquanto . Além disso, def f(Z,s=[])você deve economizar um personagem
Value Ink
@ValueInk sim, é mais lento do que a sua solução de rubi
mdahmoune
2
Padrão interessante com o recuo ...
Erik o Outgolfer
@ValueInk Vários Argumentos da função economiza mais bytes :)
mdahmoune
1
Você pode reduzir o número de bytes por mistura de tabulações e espaços
OVS
3

Ferrugem - 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)}}}}}}

Não tenho 100% de certeza se isso funciona 100% correto, mas parece estar correto para uma grande variedade de testes. Isso não é menor que o Jelly, mas pelo menos é menor que as linguagens interpretadas (até agora). Também parece ser mais rápido e pode trabalhar com entradas de um bilhão de magnitude em menos de um segundo. Por exemplo, 1234567890 + 3141592650i fatores como (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (clique aqui para testar o wolfram alpha)

Isso começou como a mesma idéia do fatoração ingênua de números inteiros, para passar por cada número abaixo do número inteiro em questão, ver se ele se divide, repetir até terminar. Então, inspirado por outras respostas, ele se transformou ... fatores repetidamente fatores em um vetor. Faz isso um bom número de vezes, mas não 'até' qualquer coisa. O número de iterações foi escolhido para cobrir uma boa parte das entradas razoáveis.

Ele ainda usa "(a mod b) == 0" para testar se um número inteiro divide outro (para Gaussianos, usamos o módulo gaussiano Rust interno e consideramos "0" como norma == 0), no entanto, verifique a 'norma ( a / b)! = 1 'evita dividir "demais", basicamente permitindo que o vetor resultante seja preenchido apenas com números primos, mas não levando nenhum elemento do vetor à unidade (0-i, 0 + i, -1 + 0i, 1 + 0i) (que é proibido pela pergunta).

Os limites do loop for foram encontrados através do experimento. y vai de 1 para cima para evitar pânico de dividir por zero ex pode ir de -999 a 0, graças ao espelhamento de gaussianos sobre os quadrantes (acho?). Quanto às limitações, a pergunta original não indicava um intervalo válido de entrada / saída, portanto, é assumido um "tamanho de entrada razoável" ... (Editar ... no entanto, não sei exatamente como calcular em que número isso será começar a "falhar", imagino que existem números inteiros gaussianos que não são divisíveis por nada abaixo de 999, mas ainda são surpreendentemente pequenos para mim)

Experimente a versão um pouco desacreditada em play.rust-lang.org

não brilhante
fonte
3

Perl 6 , 141 124 bytes

Agradecimentos 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}

Experimente online!

bb94
fonte
Como é que isso funciona? o piso é um módulo personalizado?
don bright
1
@donbright A floorparte está verificando se $_/w(ou seja, o fator atual dividido por um número) é um número inteiro
Jo King
2

Pitão , 54 51 45 42 36 bytes

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

Experimente online!

Aceita entrada no formulário 1+2j- números puramente reais ou imaginários podem omitir o outro componente (por exemplo 9, 2j). Saída é uma lista separada por nova linha de números complexos, na forma (1+2j), com números puramente imaginários omitindo a parte real.

Isso usa divisão de trilha simples, gerando todos os números inteiros gaussianos com magnitude maior que 1 e menor que o valor atual, mais o próprio valor. Eles são filtrados para manter aqueles que são um fator do valor, e o menor por magnitude é escolhido como o próximo fator principal. Isso é gerado e o valor é dividido por ele para produzir o valor para a próxima iteração.

Além disso, Pyth vence Jelly 😲 (não 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
fonte
isso é muito interessante, mas parece esgotar o tempo limite em 6840 + 585j
don bright
@donbright Faz no TIO, pois possui um limite de processamento de 60s. Ele funcionará com mais tempo; portanto, se você o estiver executando localmente, ele deverá funcionar sem problemas.
Sok