Factoriser un entier gaussien

23

Un entier gaussien est un nombre complexe dont les parties réelle et imaginaire sont des entiers.

Les entiers gaussiens, comme les entiers ordinaires, peuvent être représentés comme un produit de nombres premiers gaussiens, d'une manière unique. Le défi ici est de calculer les constituants premiers d'un entier gaussien donné.

Entrée: un entier gaussien, qui n'est pas égal à 0 et n'est pas une unité (c.-à-d. 1, -1, i et -i ne peuvent pas être donnés comme entrées). Utilisez n'importe quel format raisonnable, par exemple:

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

Sortie: une liste d'entiers gaussiens, qui sont premiers (c'est-à-dire qu'aucun d'eux ne peut être représenté comme un produit de deux entiers gaussiens non unitaires), et dont le produit est égal au nombre d'entrée. Tous les nombres dans la liste de sortie doivent être non triviaux, c'est-à-dire pas 1, -1, i ou -i. Tout format de sortie raisonnable peut être utilisé; il ne doit pas nécessairement être le même que le format d'entrée.

Si la liste des sorties contient plus d'un élément, plusieurs sorties correctes sont possibles. Par exemple, pour l'entrée 9, la sortie peut être [3, 3] ou [-3, -3] ou [3i, -3i] ou [-3i, 3i].

Cas de test, (tirés de ce tableau ; 2 lignes par cas de test)

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

Les fonctions intégrées de factorisation des entiers gaussiens ne sont pas autorisées. La factorisation d'entiers ordinaires par des fonctions intégrées est cependant autorisée.

anatolyg
la source
Devrait 3irevenir en tant que 3,i, ou 3i?
Value Ink
3iest la bonne réponse car ce in'est pas un premier choix. J'ai mis à jour le cas de test pour le rendre plus clair.
anatolyg
-3-2j, 2-1j, -1-1j est-il une bonne réponse pour la factorisation de 7 + 9j?
mdahmoune
4
Selon Wolfram Alpha, 6840+585in'a pas la bonne liste de facteurs, comme ce 5n'est pas un nombre premier gaussien. Au lieu de cela, il revient -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Source
Value Ink
1
Pour info, 256=(1+i)**16pas (1+i)**8parce que 256=2**8=(2i)**8et2i=(1+i)**2
Shieru Asakoto

Réponses:

4

Gelée , 61 55 octets

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

Essayez-le en ligne! (En-tête et pied de page formate la sortie)

-6 octets grâce à @EricTheOutgolfer

Comment ça marche

Ḟ,Ċ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
la source
quand cela dit "ne garder que le gaussien" cela signifie-t-il "ne garder que les primes"?
Don Bright
@donbright non, cela fait référence à la conservation uniquement des nombres complexes avec des composants réels et complexes
entiers
@ fireflame241 oh je vois maintenant! merci beaucoup
don bright
5

Rubis , 258 256 249 246 + 8 = 264 257 254 octets

Utilise le -rprime drapeau.

Décidément, quel gâchis.

Utilise cet algorithme 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}

Essayez-le en ligne!

Encre de valeur
la source
5

Python 2 , 250 239 223 215 octets

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:])

Essayez-le en ligne!

  • -11 octets lors de l'utilisation d' arguments de fonction multiples
  • -2² * ² octets lors de l'utilisation d'une variable pour analyser les couples (a,b)
  • -2³ octets lors du mélange des tabulations et des espaces: grâce aux ovs

Quelques explications décomposent récursivement un complexe en deux complexes jusqu'à ce qu'aucune décomposition ne soit possible ...

mdahmoune
la source
Eh bien, il expire dans TIO sur des entrées plus grandes, mais c'est plus court que ma réponse Ruby ... pour l'instant . De plus, def f(Z,s=[])devrait vous faire économiser un personnage
Value Ink
@ValueInk oui c'est plus lent que votre solution rubis
mdahmoune
2
Motif intéressant avec l'indentation ...
Erik the Outgolfer
@ValueInk Multiple Function Arguments enregistre plus d'octets :)
mdahmoune
1
Vous pouvez réduire votre nombre d'octets en mélangeant les tabulations et les espaces
ovs
3

Rouille - 212 octets

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

Je ne suis pas sûr à 100% si cela fonctionne à 100%, mais cela semble correct pour une large gamme de tests. Ce n'est pas plus petit que Jelly, mais au moins c'est plus petit que les langages interprétés (jusqu'à présent). Il semble également être plus rapide et peut fonctionner grâce à des entrées d'un milliard de magnitude en moins d'une seconde. Par exemple 1234567890 + 3141592650i facteurs comme (-9487 + 7990i) (- 1 + -1i) (- 395 + 336i) (2 + -1i) (1 + 1i) (3 + 0i) (3 + 0i) (4+ 1i) (- 1 + 1i) (- 1 + 2i), (cliquez ici pour tester sur wolfram alpha)

Cela a commencé comme la même idée que la factorisation naïve des nombres entiers, pour parcourir chaque nombre en dessous de l'entier en question, voir s'il se divise, répéter jusqu'à ce que cela soit fait. Puis, inspiré par d'autres réponses, il s'est transformé ... il factorise à plusieurs reprises des éléments dans un vecteur. Il le fait un bon nombre de fois, mais pas jusqu'à ce que quoi que ce soit. Le nombre d'itérations a été choisi pour couvrir une bonne partie des entrées raisonnables.

Il utilise toujours "(a mod b) == 0" pour tester si un entier en divise un autre (pour les gaussiens, nous utilisons le modulo gaussien intégré de Rust, et considérons "0" comme la norme == 0), cependant la vérification de 'norm ( a / b)! = 1 'empêche de diviser "trop", ce qui permet essentiellement de remplir le vecteur résultant avec uniquement des nombres premiers, mais de ne ramener aucun élément du vecteur à l'unité (0-i, 0 + i, -1 + 0i, 1 + 0i) (ce qui est interdit par la question).

Les limites pour la boucle ont été trouvées par expérience. y passe de 1 vers le haut pour éviter les paniques de division par zéro, et x peut passer de -999 à 0 grâce à la mise en miroir des Gaussiens sur les quadrants (je pense?). En ce qui concerne les limitations, la question d'origine n'indiquait pas une plage valide d'entrées / sorties, donc une "taille d'entrée raisonnable" est supposée ... (Edit ... cependant je ne sais pas exactement comment calculer à quel nombre cela va commencent à "échouer", j'imagine qu'il y a des entiers gaussiens qui ne sont pas divisibles par quoi que ce soit en dessous de 999 mais qui sont encore étonnamment petits pour moi)

Essayez la version quelque peu non golfée sur play.rust-lang.org

Don Bright
la source
3

Perl 6 , 141 124 octets

Merci à Jo King pour -17 octets

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

Essayez-le en ligne!

bb94
la source
Comment cela marche-t-il? le sol est-il un modulo sur mesure?
Don Bright
1
@donbright La floorpartie vérifie si $_/w(c'est-à-dire le facteur actuel divisé par un nombre) est un nombre entier
Jo King
2

Pyth , 54 51 45 42 36 octets

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

Essayez-le en ligne!

Accepte les entrées sous la forme 1+2j- des nombres purement réels ou imaginaires peuvent omettre l'autre composant (par exemple 9, 2j). La sortie est une liste séparée par des sauts de ligne de nombres complexes, sous la forme (1+2j), avec des nombres purement imaginaires omettant la partie réelle.

Cela utilise une simple division de piste, générant tous les entiers gaussiens de magnitude supérieure à 1 et inférieure à la valeur actuelle, plus la valeur elle-même. Ceux-ci sont filtrés pour conserver ceux qui sont un facteur de la valeur, et le plus petit en magnitude est choisi comme facteur premier suivant. Il s'agit d'une sortie, et la valeur est divisée par celle-ci pour produire la valeur pour la prochaine itération.

Aussi, Pyth bat Jelly 😲 (je ne m'attends pas à ce que ça 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
la source
c'est très intéressant mais il semble expirer sur 6840 + 585j
don bright
@donbright Il le fait sur TIO, car il a une limite de traitement de 60s. Cela fonctionnera avec plus de temps, donc si vous l'exécutez localement, cela devrait fonctionner sans problème.
Sok