Encuentra Primes en Pi

30

Los primos están en todas partes ...

se esconden dentro de Pi

3.141592653 58979 3238 462643 3832 795028841 971693993751

¡Consigamos esos primos!

El reto

Dado como entrada un número entero n>0, descubra cuántos primos están ocultos dentro de los primeros ndígitos dePi

Ejemplos

Porque n=3debemos buscar primos en [3,1,4]. Hay 2 Primes (3,31), por lo que su código debería generar 2
Para n=10, los primeros 10 dígitos son [3,1,4,1,5,9,2,6,5,3]y su código debería generar 12porque [2, 3, 5, 31, 41, 53, 59, 653, 4159, 14159, 314159, 1592653]estaban ocultos (¡y encontrados!)

Casos de prueba

entrada -> salida

1->1  
3->2  
13->14  
22->28  
42->60  
50->93

150->197  
250->363  
500->895

Reglas

Su código debe poder encontrar todos los números primos, al menos paran=50
Sí, puede codificar los primeros 50 dígitos de Pisi le gusta
.

Este es el ¡La respuesta más corta en bytes gana!


fuente
66
"puedes codificar los primeros 50 dígitos de Pi si quieres" . ¡Primer problema resuelto! Ahora para la prueba de primalidad de golf en enteros de hasta 50 dígitos ... O_o (Este es un buen desafío, pero probablemente se requieren sólidas incorporaciones matemáticas o bibliotecas).
Arnauld
3
@totallyhuman ¡Esa secuencia ni siquiera está en OEIS todavía! ¿Es hora de que reclames fama?
Sanchises
3
La OMI que permite la codificación de los primeros 50 valores es perjudicial para este desafío. Este desafío consiste básicamente en dos partes, 1) tratar de comprimir los primeros 50 valores, o 2) realmente hacer el desafío.
JAD
2
Por lo general, en este tipo de desafíos, donde el cálculo se vuelve más difícil / lento / intensivo en memoria, es suficiente que el programa trabaje teóricamente, en lugar de establecer un límite arbitrario y permitir la codificación rígida.
JAD
3
@BillSteihn Actualizar las reglas después de que haya varias respuestas va en contra del espíritu de este sitio web. ¿Has publicado esta pregunta en el Sandbox ? Habría recibido comentarios muy pronto sobre las respuestas codificadas.
Olivier Grégoire

Respuestas:

20

05AB1E ,  10  8 bytes

-2 bytes gracias a Adnan ( pvectorises)

<žsþŒÙpO

Pruébalo en línea! (funcionará hasta n = 98413 pero será muy lento incluso para n = 50 debido a la necesidad de probar números tan grandes para primalidad - TIO agota el tiempo de espera en 60 segundos para n = 50).

¿Cómo?

<žsþŒÙpO - implicitly push input, n
<        - decrement = n-1
 žs      - pi to that many decimal places (i.e. to n digits)
   þ     - only the digits (get rid of the decimal point)
    Œ    - all sublists
     Ù   - unique values
      p  - is prime? (vectorises) 1 if so, 0 otherwise
       O - sum
         - implicitly print the top of the stack
Jonathan Allan
fuente
<žsþŒÙpOdebería funcionar para 8 bytes
Adnan
Ah, sí pvectorises gracias!
Jonathan Allan
2
¡Sí! Finalmente, una respuesta de código de golf muy breve que realmente entiendo. : D
Fabian Röling
11

Mathematica, 76 bytes

Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&
J42161217
fuente
Oh, no es justo, no estoy familiarizado con el golf Mathematica. : P (+1)
totalmente humano
@totallyhuman Publicamos esto al mismo tiempo. ¡esto es tan extraño!
J42161217
Jugué mi respuesta usando algunos de los trucos sintácticos, pero mantuve las funciones que usaba antes. Espero que no te moleste.
Totalmente humano
Tr[1^...]Esa es una forma inteligente de encontrar la longitud de la lista, ¡bien!
numbermaniac
6

Mathematica, 104 97 90 bytes

Length@DeleteDuplicates@Select[FromDigits/@Subsequences@First@RealDigits[Pi,10,#],PrimeQ]&

Jajajaja, logré hacer que esto funcione. No tengo idea de cómo usar Mathematica. XD

Entrada:

[50]
totalmente humano
fuente
1
publicaste unos segundos por delante de mí. ¡y nuestras respuestas son muy parecidas! +1
J42161217
¿Está seguro de los números que acaba de publicar (verifique el redondeo de los dígitos) Veo resultados ligeramente diferentes usando Python y sympy
Jonathan Allan
@JonathanAllan 50 96El OP dice que 50 dígitos contienen 93 primos, por lo que la precisión de Sympy podría estar apagada ...
Totalmente humano el
@JonathanAllan ¿Sympy está utilizando una prueba de primitiva probabilística o determinista? (La misma pregunta para PrimeQ de Mathematica.)
Arnauld
@Arnauld buen punto, no estoy seguro.
Jonathan Allan
3

Python 3 , 274 237 207 194 189 bytes

-37 bytes gracias a Wheat Wizard! -14 bytes gracias a Mr.Xcoder.

Codifica los primeros 50 dígitos de pi pero calcula manualmente todo lo demás.

x=int(input());l="31415926535897932384626433832795028841971693993751"[:x]
print(sum(all(i%m for m in range(2,i))for i in{int(i)for w in range(x)for i in[l[j:j-~w]for j in range(x-w)]}-{1}))

Pruébalo en línea!

totalmente humano
fuente
l=list("31415...)debería guardar ~ 40 caracteres. Y ese cambio te permite reemplazar map(str,i)con solo i.
AShelly
195 bytes eliminando un código extraño.
Sr. Xcoder
194 bytes declarandolen(l)
Sr. Xcoder
1

R, 156 123 bytes

cat(cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))[scan()])

Solución súper interesante. Trabajando en una adecuada.

Guardado 33 bytes gracias a @Giuseppe.

R (+ números y gmp), 198 bytes

function(n,x=unique(gmp::as.bigz(unlist(sapply(1:n,function(x)substring(gsub("[.]","",numbers::dropletPi(50)),x,x:n))))))min(length(x),sum(sapply(sapply(x[x>0&!is.na(x)],gmp::factorize),length)==1))

Solución adecuada Toma ncomo entrada.

Utiliza numbers::dropletPi(50)para generar los primeros 50 lugares decimales de pi. gsubelimina el punto decimal. substringtoma todas las subcadenas posibles (sorpresa sorpresa) de pi hasta n.

La lista devuelta se aplana y se convierte en gmp's bigzformato. Este formato es necesario para almacenar enteros de longitud 50. uniquetoma los valores únicos de ese vector. Este resultado se almacena en x.

Luego verificamos la primalidad. Esto es complicado, porque hay un montón de casos extremos y molestias:

  • Para alto n, hay un 0en pi. Esto conduce a subcadenas con un cero a la izquierda. as.bigzproduce NAs con eso, que debe eliminarse.

  • En una nota similar, la subcadena "0"se bloqueará gmp::factorize, por lo que también debe eliminarse.

  • Para n=1, x = 3. Lo cual en sí mismo está bien, pero la bigzrepresentación de 3es iterable, por sapplylo que se confundirá e informará 16 primos. Para este fin, tomamos el mínimo de la longitud del vector xy la cantidad de primos en él.

  • gmp::isprimeparece que no puede manejar confiablemente los grandes números de manera confiable. Entonces, en su lugar, usamos gmp::factorizey verificamos que la longitud de la salida es 1.

Entonces, en general, eliminamos 0y NAde x. Factorizamos todo xy verificamos la longitud. Contamos el número de ocurrencias de 1y devolvemos el min(occurences, length(x)).

JAD
fuente
¡Ahí tienes! Ahora veamos si alguien puede superar esto con una solución más interesante. ¡Podrías ser tú!
use en cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))lugar de su vector para 123 bytes :)
Giuseppe
@Giuseppe Una buena. Esa 'compresión' definitivamente superará cualquier solución legítima.
JAD
Creo que es imposible en R sin codificar o introducir otro paquete ya que R solo tiene entradas de 32 bits, lo que ciertamente no representará un número entero de 50 dígitos.
Giuseppe
1
Sí, puedo pensar en esto un poco más también. 82 bytes codificados
Giuseppe
0

Gelatina , 59 32 bytes

-27 bytes gracias a Erik the Outgolfer.

“!⁶⁷¬,6½ạEC.wʠ€Ẉ!+Ẉfṭ¡’Ṿḣ³ẆVQÆPS

Pruébalo en línea!

Explicación

“...’Ṿḣ³ẆVQÆPS

“...’           compressed string that evaluates to first 50 digits of pi (314159...)
     Ṿ          uneval; stringify
      ḣ³        first n characters of the string where n is the first command-line argument
        Ẇ       all sublists
         V      convert all elements to integers
          Q     deduplicate
           ÆP   convert all prime elements to 1 and others to 0
             S  sum
totalmente humano
fuente
¿Por qué enviaste esto con respuestas?
Zacharý
Porque nadie más estaba respondiendo, y de todos modos presioné cap cap. : P
totalmente humano