Eisenstein integers are complex numbers of the form


Where a,b are integers, and

ω = e^(2πi/3)

The Eisenstein integers form a triangular lattice in the complex plane:

Eisenstein Integers in the Complex Plane

We say that an Eisenstein integer z=a+bω is prime if it cannot be written as the product of two non-unit (not 1,-1,ω,-ω,ω^2, or -ω^2) Eisenstein integers


Input: A natural number n.

Output: The number of Eisenstein primes which are of the form a+bω for which a,b are natural numbers (including zero) less than or equal to n

Test Cases

0 → 0

1 → 0

2 → 5

3 → 9

4 → 13

5 → 20


This is code-golf, so least amount of bytes wins

  • 2
    \$\begingroup\$ Could you provide some test cases? \$\endgroup\$
    – Alex A.
    Commented Jun 13, 2016 at 0:35
  • \$\begingroup\$ I don't understand the test cases. The number of a,b pairs for 2 is only 4 so how could 5 of them be prime? \$\endgroup\$
    – Maltysen
    Commented Jun 13, 2016 at 1:07
  • \$\begingroup\$ @Maltysen let me rewrite the definition \$\endgroup\$
    – Meow Mix
    Commented Jun 13, 2016 at 1:20
  • 1
    \$\begingroup\$ @user3502615 i'm talking about the part where you say "are of the form a+bω for which a,b are natural numbers (including zero) less than n" \$\endgroup\$
    – Maltysen
    Commented Jun 13, 2016 at 1:29
  • \$\begingroup\$ @Maltysen There are 5 numbers: 2ω, 2ω+1,2ω+2,ω+2, and 2 \$\endgroup\$
    – Meow Mix
    Commented Jun 13, 2016 at 4:05

3 Answers 3


Julia, 66 62 60 bytes

!n=sum(isprime,[a<1<b%3?b:a^2-a*b+b^2for a=[0;0;0:n],b=0:n])

Try it online!


We’re interested in the primes in this parallelogram on the complex plane (example for n = 4):

enter image description here

We can split them into primes on the green lines, and on the gray lines.

Wikipedia tells me an Eisenstein number z is a green line Eisenstein prime iff |z| is a natural prime equal to 2 mod 3.

It also says z is a gray line Eisenstein prime iff |z|² = a² − ab + b² is a natural prime.

So we loop over a = 0…n and b = 0…n, and check:

  • If (a = 0 or b = 0 or a = b) and max(a, b) % 3 = 2, then count whether max(a, b) is a prime.

  • Else, count whether a² − ab + b² is a prime.

However, we can abuse the distribution’s symmetry. Instead of counting each green line once, we can just count one green line thrice! That is, only check a = 0 and increment the counter by three when we find a green line prime. The a=[0;0;0:n] achieves exactly this.

Since we know we’re only considering the green line a = 0, we can replace max(a, b) by b.

The “green line condition” is nicely expressed in Julia using operator chaining: a<1<b%3.

(For the remaining green lines, we will never return a false positive: if a = b or b = 0 then a² − ab + b² = a², which can’t be prime.)


Maybe, instead of writing a^2-a*b+b^2, I can conditionally replace the exponent at b by 1 when a<1<b%3 – then the expression reduces to b. This doesn’t seem to be shorter, but it’s neat!


Jelly, 24 bytes


Roughly the same approach as my Julia answer.

                          Initial argument: n
R                           Compute [1, 2, …, n]
 ð_²+×                      (λ, ρ) —→ (λ − ρ)² + λρ (which is λ² − λρ + ρ²)
      µ€                    Zip with itself. Call this Q.

        µ                 Refocus argument: Q
         ³                  The initial argument n
          RḊm3              Compute candidate green line primes: [2, 5, 8, …, n]
              ,             Call this P. Make pair with argument.

               µ          Refocus argument: [P, Q]
                ÆP          Check primality
                  ×1¦3      Multiply the first element by 3
                      FS    Sum everything
                            (The result is 3·countprimes(P) + countprimes(Q))

CJam (34 bytes)


Online demo


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.