Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python 3 - Gaussian divisors of a Gaussian integer

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)]
like image 300
srm Avatar asked Jan 15 '17 16:01

srm


1 Answers

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.

like image 98
MSeifert Avatar answered Oct 24 '22 11:10

MSeifert