8
\$\begingroup\$

Introduction

Eisenstein integers are complex numbers of the form

a+bω

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

Program

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

Scoring

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

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you provide some test cases? \$\endgroup\$ – Alex A. Jun 13 '16 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 Jun 13 '16 at 1:07
  • \$\begingroup\$ @Maltysen let me rewrite the definition \$\endgroup\$ – Meow Mix Jun 13 '16 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 Jun 13 '16 at 1:29
  • \$\begingroup\$ @Maltysen There are 5 numbers: 2ω, 2ω+1,2ω+2,ω+2, and 2 \$\endgroup\$ – Meow Mix Jun 13 '16 at 4:05
1
\$\begingroup\$

Jelly, 24 bytes

Rð_²+×µ€µ³RḊm3,µÆP×1¦3FS

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))
\$\endgroup\$
8
\$\begingroup\$

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!

Explanation

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.)

Ideas

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!

\$\endgroup\$
1
\$\begingroup\$

CJam (34 bytes)

qi,:)_2m*{_:*\:-_*+}%\1>3%3*+:mp1b

Online demo

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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