Contando primos de Eisenstein

8

Introducción

Los enteros de Eisenstein son números complejos de la forma

a+bω

¿Dónde a,bestán los enteros y

ω = e^(2πi/3)

Los enteros de Eisenstein forman una red triangular en el plano complejo:

Eisenstein enteros en el plano complejo

Decimos que un número entero de Eisenstein z=a+bωes primo si no puede escribirse como el producto de dos números enteros de Eisenstein no 1 (-1, -1, ω, -ω, ω ^ 2 o -ω ^ 2)

Programa

Entrada : un número natural n.

Salida : El número de primos de Eisenstein que tienen la forma a+bωpara la que a,bson números naturales (incluido cero) menores o iguales quen

Casos de prueba

0 → 0

1 → 0

2 → 5

3 → 9

4 → 13

5 → 20

Puntuación

Esto es code-golf, entonces gana la menor cantidad de bytes

Mezcla Miau
fuente
2
¿Podría proporcionar algunos casos de prueba?
Alex A.
No entiendo los casos de prueba. El número de a,bpares 2solo es 4así, ¿cómo podrían 5ser primos?
Maltysen
@Maltysen me deja reescribir la definición
Meow Mix
1
@ user3502615 estoy hablando de la parte en la que dice "son de la forma a + bω para las cuales a, b son números naturales (incluido cero) menores que n"
Maltysen
@Maltysen Hay 5 números: 2ω, 2ω + 1,2ω + 2, ω + 2 y 2
Meow Mix

Respuestas:

1

Jalea, 24 bytes

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

Aproximadamente el mismo enfoque que mi respuesta de Julia.

                          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))
Lynn
fuente
8

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

Pruébalo en línea!

Explicación

Estamos interesados ​​en los números primos en este paralelogramo en el plano complejo (ejemplo para n = 4 ):

ingrese la descripción de la imagen aquí

Podemos dividirlos en números primos en las líneas verdes y en las líneas grises .

Wikipedia me dice que un número de Eisenstein z es una línea verde Eisenstein prime iff | z | es un primo natural igual a 2 mod 3.

También dice que z es una línea gris Eisenstein prima iff | z | ² = a² - ab + b² es una prima natural.


Por lo tanto, un bucle sobre un = 0 ... n y b = 0 ... n , y el cheque:

  • Si (a = 0 o b = 0 o a = b) y max (a, b)% 3 = 2 , cuente si max (a, b) es primo.

  • De lo contrario, cuente si a² - ab + b² es primo.

Sin embargo, podemos abusar de la simetría de la distribución. En lugar de contar cada línea verde una vez, ¡solo podemos contar una línea verde tres veces! Es decir, solo verifique a = 0 e incremente el contador en tres cuando encontremos una línea verde prima. Lo a=[0;0;0:n]logra exactamente esto.

Como sabemos que solo estamos considerando la línea verde a = 0 , podemos reemplazar max (a, b) por b .

El “estado de la línea verde” está muy bien expresado en el uso de Julia Secuencia de operadores: a<1<b%3.

(Para las líneas verdes restantes, nunca devolveremos un falso positivo: si a = b o b = 0 entonces a² - ab + b² = a² , que no puede ser primo).

Ideas

Tal vez, en lugar de escribir a^2-a*b+b^2, puedo reemplazar condicionalmente el exponente al bpor 1si a<1<b%3- entonces la expresión se reduce a b. Esto no parece ser más corto, ¡pero está ordenado!

Lynn
fuente