gaussian-primes.egi

-- Gaussian primes: primes in Z[i]

-- Generate Gaussian integers and their norms
def gaussianNorms : [(MathExpr, MathExpr)] :=
  map (\(x, y) -> (x + y * i, (x + y * i) * (x - y * i)))
      (matchAll take 10 nats as set integer with
        | $x :: $y :: _ -> (x, y))

assertEqual "first few Gaussian integers with norms"
  (take 10 gaussianNorms)
  [(1 + i, 2), (1 + 2 * i, 5), (2 + i, 5), (1 + 3 * i, 10), (2 + 2 * i, 8),
   (3 + i, 10), (1 + 4 * i, 17), (2 + 3 * i, 13), (3 + 2 * i, 13), (4 + i, 17)]

-- Filter to get Gaussian primes (those with prime norm)
def gaussianPrimes : [(MathExpr, MathExpr)] :=
  filter
    (\(_, n) -> isPrime n)
    (map (\(x, y) -> (x + y * i, (x + y * i) * (x - y * i)))
         (matchAll take 10 nats as set integer with
           | $x :: $y :: _ -> (x, y)))

assertEqual "Gaussian primes"
  gaussianPrimes
  [(1 + i, 2), (1 + 2 * i, 5), (2 + i, 5), (1 + 4 * i, 17), (2 + 3 * i, 13),
   (3 + 2 * i, 13), (4 + i, 17), (1 + 6 * i, 37), (2 + 5 * i, 29),
   (5 + 2 * i, 29), (6 + i, 37), (2 + 7 * i, 53), (4 + 5 * i, 41),
   (5 + 4 * i, 41), (7 + 2 * i, 53), (1 + 10 * i, 101), (3 + 8 * i, 73),
   (5 + 6 * i, 61), (6 + 5 * i, 61), (8 + 3 * i, 73), (10 + i, 101),
   (3 + 10 * i, 109), (4 + 9 * i, 97), (5 + 8 * i, 89), (8 + 5 * i, 89),
   (9 + 4 * i, 97), (10 + 3 * i, 109), (7 + 8 * i, 113), (8 + 7 * i, 113),
   (7 + 10 * i, 149), (10 + 7 * i, 149), (9 + 10 * i, 181), (10 + 9 * i, 181)]