Python 3 - Gaussian divisors of a Gaussian integer

Question

I'm trying to write a method to generate a sequence of Gaussian divisors of a Gaussian integer - a Gaussian integer is either a normal integer or a complex number g = a + bi where a and b are both integers, and a Gaussian divisor of a Gaussian integer g is a Gaussian integer d such that g / d is also a Gaussian integer.

I've got the following code.

def is_gaussian_integer(c):
    """
        Checks whether a given real or complex number is a Gaussian integer,
        i.e. a complex number g = a + bi such that a and b are integers.
    """
    if type(c) == int:
        return True
    return c.real.is_integer() and c.imag.is_integer()


def gaussian_divisors(g):
    """
        Generates a sequence of Gaussian divisors of a rational or Gaussian
        integer g, i.e. a Gaussian integer d such that g / d is also a Gaussian integer.
    """
    if not is_gaussian_integer(g):
        return
    if g == 1:
        yield complex(g, 0)
        return
    g = complex(g) if type(g) == int or type(g) == float else g
    a = b = 1
    ubound = int(math.sqrt(abs(g)))
    for a in range(-ubound, ubound + 1):
        for b in range(-ubound, ubound + 1):
            if a or b:
                d = complex(a, b)
                if is_gaussian_integer(g / d):
                    yield d
    yield g

It seems to "mostly" work but for some inputs it is missing out some Gaussian divisors, e.g. for 2 I would expect the sequence to include the divisor -2 + 0j (which is just -2), but it is missing. I can't figure out why it is doing this or where there is gap in the logic.

In [92]: list(gaussian_divisors(2))
Out[92]: [(-1-1j), (-1+0j), (-1+1j), -1j, 1j, (1-1j), (1+0j), (1+1j), (2+0j)]

In python 3 the integer division operator is `//`, not `/`. I have no idea what is does with complex operands. — President James K. Polk, Jan 15 '17 at 16:27
I don't think the `//` operator applies to complex numbers, e.g. `1 / 1j` gives you `-1j` as expected but `1 // -1j` throws an error: `TypeError: can't take floor of complex number.`. This is probably because there is no natural ordering of complex numbers unlike integers. — srm, Jan 15 '17 at 16:33
ok, you'll probably want to define your own divisibility operator as `/` won't work correctly for large enough operands. Also, for `g=2`, `ubound = 1`, so your loop goes from -1 to 1. You never test -2. — President James K. Polk, Jan 15 '17 at 16:34
Your condition `if g == 1: yield complex(g, 0) return` is incorrect. The divisors of `1` are `1, -1, i, -i`. — Stef, Jan 27 '23 at 14:26
I recommend reading the enlightening answer to this question: [What's a nice method to factor Gaussian integers?](https://stackoverflow.com/questions/2269810/whats-a-nice-method-to-factor-gaussian-integers) — Stef, Jan 27 '23 at 14:29

score 1 · Accepted Answer · answered Jan 15 '17 at 16:36

Instead of just yielding

yield g

you could additionally

yield -g

Because your loops start and stop at int(math.sqrt(abs(g))) = int(sqrt(2)) which is just 1 so it will just test -1, 0 and 1.

Alternativly if you want to include -2 and 2 in your loops you need to either increment the ubound or math.ceil the sqrt result.

Python 3 - Gaussian divisors of a Gaussian integer

1 Answers1