Factorize a Gaussian integer

Question

A Gaussian integer is a complex number whose real and imaginary parts are integers.

Gaussian integers, like ordinary integers, can be represented as a product of Gaussian primes, in a unique manner. The challenge here is to calculate the prime constituents of a given Gaussian integer.

Input: a Gaussian integer, which is not equal to 0 and is not a unit (i.e. 1, -1, i and -i can not be given as inputs). Use any sensible format, for example:

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

Output: a list of Gaussian integers, which are prime (i.e. no one of them can be represented as a product of two non-unit Gaussian integers), and whose product is equal to the input number. All numbers in the output list must be non-trivial, i.e. not 1, -1, i or -i. Any sensible output format can be used; it should not necessarily be the same as input format.

If the output list has more than 1 element, then several correct outputs are possible. For example, for input 9 the output can be [3, 3] or [-3, -3] or [3i, -3i] or [-3i, 3i].

Test cases, (taken from this table; 2 lines per test case)

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

Built-in functions for factoring Gaussian integers are not allowed. Factoring ordinary integers by built-in functions is allowed though.

• Value Ink: Should 3i return as 3,i, or 3i?
• anatolyg: 3i is the correct answer because i is not a prime. I have updated the test case to make it clearer.
• mdahmoune: is -3-2j, 2-1j, -1-1j a correct answer for factorization of 7+9j ?
• Value Ink: According to Wolfram Alpha, 6840+585i has the wrong list of factors, as 5 is not a Gaussian prime. Instead, it returns -1-2i, 1+4i, 2+i, 3, 3, 6+i, 6+i. Source
• Shieru Asakoto: FYI, 256=(1+i)**16 not (1+i)**8 because 256=2**8=(2i)**8 and 2i=(1+i)**2

Answer 1

Ruby, (削除) 258 (削除ここまで) (削除) 256 (削除ここまで) (削除) 249 (削除ここまで) 246+8 = (削除) 264 (削除ここまで) (削除) 257 (削除ここまで) 254 bytes

Uses the -rprime flag.

Geez, what a mess.

Uses this algorithm from 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}

Try it online!

Answer 2

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

Try it online!

• -11 bytes when using Multiple Function Arguments
• -22*2 bytes when using one variable to parse couples (a,b)
• -23 bytes when mixing tabs and spaces: thanks to ovs

Some explanation recursively decompose a complex to two complexes until no decomposition is possible...

• Value Ink: Well, it times out in TIO on larger inputs, but it's shorter than my Ruby answer... for now. Also, def f(Z,s=[]) should save you a character
• mdahmoune: @ValueInk yes it's slower than your ruby solution
• Erik the Outgolfer: Interesting pattern with the indentation...
• mdahmoune: @ValueInk Multiple Function Arguments saves more bytes :)
• ovs: You can reduce your byte count by mixing tabs and spaces

Answer 3

Jelly, (削除) 61 (削除ここまで) (削除) 55 (削除ここまで) 50 bytes

ÆiḤp/-,1p×ばつ1,ıFs2S8ドル÷ÆiḞƑ$ƇỊÐḟ1;Ṫð,÷@\ḟ1
Ç€F$ÐL

Try it online! (Header and Footer formats the output)

-6 bytes thanks to @EricTheOutgolfer

-5 bytes thanks to @caird coinheringaahing

How it Works

ÆiḤp/-,1p×ばつ1,ıFs2S8ドル÷ÆiḞƑ$ƇỊÐḟ1;Ṫð,÷@\ḟ1 - helper: outputs a factor pair of the input
ÆiḤ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 
8÷ - get quotient with input complex number
 ÆiḞƑ$Ƈ - keep only Gaussian numbers (those unchanged when complex parts are floored)
 ỊÐḟ - 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

• Erik the Outgolfer: You can get 6 bytes down...and golf your header and footer by much too!
• don bright: when this says "keep only Gaussian" does it mean "keep only Primes"?
• fireflame241: @donbright no, it refers to keeping only those complex numbers with integer real and complex components
• don bright: @fireflame241 oh i see now! thank you very much
• caird coinheringaahing: -5 bytes with the newer version of Jelly

Answer 4

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

I'm not 100% sure if this works 100% correct, but it seems to be correct for a large range of tests. This isn't smaller than Jelly, but at least it is smaller than the interpreted languages (so far). It also seems to be faster and can work through inputs of a billion magnitude in less than a second. For example 1234567890+3141592650i factors as (-9487+7990i)(-1+-1i)(-395+336i)(2+-1i)(1+1i)(3+0i)(3+0i)(4+1i)(-1+1i)(-1+2i), (click here to test on wolfram alpha)

This started out as the same idea as naive factoring of integers, to go through each number below the integer in question, see if it divides, repeat until done. Then, inspired by other answers, it morphed... it repeatedly factors items in a vector. It does this a good number of times, but not 'until' anything. The number of iterations has been chosen to cover a good chunk of reasonable inputs.

It still uses "(a mod b) == 0" to test whether one integer divides another (for Gaussians, we use builtin Rust gaussian modulo, and consider "0" as norm == 0), however the check for 'norm(a/b) != 1' prevents dividing "too much", basically allowing the resulting vector to be filled with only primes, but not taking any element of the vector down to unity (0-i,0+i,-1+0i,1+0i) (which is prohibited by the question).

The for-loop limits were found through experiment. y goes from 1 up to prevent divide-by-zero panics, and x can go from -999 to 0 thanks to the mirroring of Gaussians over the quadrants (I think?). As regarding the limitations, the original question did not indicate a valid range of input/output, so a "reasonable input size" is assumed... (Edit... however i am not exactly sure how to calculate at which number this will begin to "fail", i imagine there are Gaussian integers that are not divisible by anything below 999 but are still surprisingly small to me)

Try the somewhat ungolfed version on play.rust-lang.org

Answer 5

Perl 6, (削除) 141 (削除ここまで) 124 bytes

Thanks to Jo King for -17 bytes

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

Try it online!

• don bright: how does this work? is the floor a custom built modulo?
• Jo King: @donbright The floor part is checking if $_/w (i.e. the current factor divided by a number) is a whole number

Answer 6

Pyth, (削除) 54 (削除ここまで) (削除) 51 (削除ここまで) (削除) 45 (削除ここまで) (削除) 42 (削除ここまで) 36 bytes

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

Try it online!

Accepts input in the form 1+2j - purely real or imaginary numbers can omit the other component (e.g. 9, 2j). Output is a newline-separated list of complex numbers, in the form (1+2j), with purely imaginary numbers omitting the real part.

This uses simple trail division, generating all gaussian integers with magnitude greater than 1 and less than the current value, plus the value itself. These are filtered to keep those that are a factor of the value, and the smallest by magnitude is chosen as the next prime factor. This is output, and the value is divided by it to produce the value for the next iteration.

Also, Pyth beating Jelly 😲 (I don't expect it to last though)

 .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

• don bright: this is very interesting but it appears to timeout on 6840+585j
• Sok: @donbright It does on TIO, as it has a processing limit of 60s. It will work with more time, so if you are running it locally it should work without issue.

Answer 7

Python 3.12+, (削除) 690 (削除ここまで) (削除) 687 (削除ここまで) (削除) 577 (削除ここまで) (削除) 553 (削除ここまで) 538 bytes

^{-003 bytes
-110 bytes thanks to @ceilingcat and @CrSb0001
-024 bytes thanks to @ceilingcat and @CrSb0001
-015 bytes thanks to @ceilingcat and @CrSb0001}

A=abs
R=lambda z:round(z.real)+round(z.imag)*1j
def G(a,b):
 if A(a)<A(b):a,b=b,a
 return G(b,r)if(r:=a-R(a/b)*b)else b
def C(n):
 a=[];N=int(A(n)**2);s=[1>0]*N;s[0]=s[1]=F=1>1;s[4::2]=[F]*(N-3>>1)
 for i in range(3,-~int(N**.5)):
 if s[i]:s[i*i::2*i]=(~-N+i*(2-i))//2//i*[F]
 for p in[i for i,v in enumerate(s)if v]:
 while N%p<1:N//=p;a+=p,
 F,P,*z=a,1
 while[]<F:
 if(a:=F.pop(0))%4>2:u=a;F.pop(0)
 else:
 while P<a!=-~pow(P:=P+1,~-a//2,a):1
 if (n-(u:=G(a,pow(P,~-a//4,a)+1j))*R(n/u)):u-=u.imag*2j
 n/=u;z+=R(u),
 return z[:-1]+[z[-1]*R(n)]

Admittedly likely my worst Python golf, it could definitely be improved. At least it passes all of the test-cases with no problem.

Also I am very glad that $3ドル\cdot3\cdot(2+i)(-1-2i)(4-i)(6+i)(-1+6i)=6840+585i$$and that all factors mentioned above are all prime in \$\mathbb Z[i]\$, I would not have enjoyed bug-fixing that.

The main method I used to factorize the Gaussian integers was to try to look for prime factors in the rectangle$$((I+Ji),(-I+Ji),(-I-Ji),(I-Ji))$$ where \$I,J=|z.\text{real}|,|z.\text{imag}|\$.

---

Original try it online! Link contains the main test-cases I was most worried about failing.

Try it online!

• CrSb0001: @ceilingcat That's impressive! I actually had it golfed even further to 674 but wasn't expecting it to go much lower!

Answer 8

APL(NARS), 146 chars

r←g w;s;l;i;j;m
s←-l←⌈/3+⌊√∣(3○しろまるw),11○しろまるw⋄r←∅⋄i←l⋄→5
j←l×ばつ⍳(1≥∣m)∨w=m←<i ×ばつ⍳s&l×ばつ⍳s<i-←1
q←{∅=k←g⍵:⍵⋄(∇⍵÷k),∇k}

//16+たす34+たす4+たす48+たす11+たす11+たす22=わ146

The function make answers to exercise is the recursive function q that has as input one complex number (written as aJb as a+ib) and return a list of complex numbers.

Here I suppose that the factors aJb have both a and b less than 3+⌊√∣(3○しろまるw),11○しろまるw.

It seems ok in the few test... I'm not sure if each factor is prime. Test:

 q 2
1J ̄1 1J1 
 q 0J3
0J3 
 q 256
 ̄1J ̄1 1J1 1J ̄1 1J1 1J ̄1 1J1 1J1 1J ̄1 1J1 1J ̄1 1J1 1J1 1J ̄1 1J1 1J ̄1 1J1 
 ×ばつ/q 256
256J0 
 q 7J9
1J2 1J ̄1 3J2 
 ×ばつ/q 7J9
7J9 
 q 27J15
7J ̄2 1J1 3J0 
 q 6840J585
1J ̄6 1J2 3J0 2J1 3J0 1J ̄6 1J4 
 ×ばつ/q 6840J585
6840J585 

It seems that each result Number in the list Is a Gaussian prime, without apply the definition of Gaussian prime.