def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n % 2 == 0: return False
  if n < 9: return True
  if n % 3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:
    if n % f == 0: return False
    if n % (f+2) == 0: return False
    f += 6
  return True

def is_gaussian_prime(num):
    a = num.real
    b = num.imag
    if a == 0:
        b = abs(b)
        return is_prime(b) and b % 4 == 3
    elif b == 0:
        a = abs(a)
        return is_prime(a) and a % 4 == 3
    return is_prime(a**2 + b**2)

numInComplexBase = [0]
base = -1 - 1j

#Check the first x numbers in the complex base
x = 10000
for index in range(1, x + 1):
    # Row index of the binary tree constructed from the values of numInComplexBase
    row = index.bit_length() - 1
    leadingValue = base**row
    theRest = numInComplexBase[index - 2**row]
    number = leadingValue + theRest

    numInComplexBase.append(number)
    if is_gaussian_prime(number):
        print(index)