Eisenstein Primes

Apr 13 2016
Eisenstein Primes

-- Eisenstein primes: primes in Z[w] where w = (-1 + sqrt(3)*i) / 2

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

assertEqual "first few Eisenstein integers with norms"
  (take 10 eisensteinNorms)
  [(1 + w, 1), (1 + 2 * w, 3), (2 + w, 3), (1 + 3 * w, 7), (2 + 2 * w, 4),
   (3 + w, 7), (1 + 4 * w, 13), (2 + 3 * w, 7), (3 + 2 * w, 7), (4 + w, 13)]

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

assertEqual "Eisenstein primes"
  eisensteinPrimes
  [(1 + 2 * w, 3), (2 + w, 3), (1 + 3 * w, 7), (3 + w, 7),
   (1 + 4 * w, 13), (2 + 3 * w, 7), (3 + 2 * w, 7), (4 + w, 13), (1 + 6 * w, 31),
   (2 + 5 * w, 19), (3 + 4 * w, 13), (4 + 3 * w, 13), (5 + 2 * w, 19),
   (6 + w, 31), (1 + 7 * w, 43), (3 + 5 * w, 19), (5 + 3 * w, 19), (7 + w, 43),
   (1 + 9 * w, 73), (3 + 7 * w, 37), (7 + 3 * w, 37), (9 + w, 73),
   (2 + 9 * w, 67), (4 + 7 * w, 37), (5 + 6 * w, 31), (6 + 5 * w, 31),
   (7 + 4 * w, 37), (9 + 2 * w, 67), (3 + 10 * w, 79), (4 + 9 * w, 61),
   (6 + 7 * w, 43), (7 + 6 * w, 43), (9 + 4 * w, 61), (10 + 3 * w, 79),
   (5 + 9 * w, 61), (9 + 5 * w, 61), (7 + 9 * w, 67), (9 + 7 * w, 67),
   (7 + 10 * w, 79), (8 + 9 * w, 73), (9 + 8 * w, 73), (10 + 7 * w, 79)]
Links

Back to the Table of Contents