No, no quiero decir ϕ = 1.618...
y π = 3.14159...
. Me refiero a las funciones .
- φ (x) es el número de enteros menores o iguales a los
x
que son relativamente primosx
. - π (x) es el número de primos menores o iguales que
x
. - Digamos que "no pi" es entonces π̅ (x) y defínalo como el número de compuestos menores o iguales a
x
.
Tarea
Dado un entero estrictamente positivo x
, calcule φ (π̅ (x)) . La puntuación está en bytes.
Ejemplos
Cada línea consta de la entrada (de 1 a 100, inclusive) y la salida correspondiente separada por un espacio.
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 2
10 4
11 4
12 2
13 2
14 6
15 4
16 6
17 6
18 4
19 4
20 10
21 4
22 12
23 12
24 6
25 8
26 8
27 16
28 6
29 6
30 18
31 18
32 8
33 12
34 10
35 22
36 8
37 8
38 20
39 12
40 18
41 18
42 12
43 12
44 28
45 8
46 30
47 30
48 16
49 20
50 16
51 24
52 12
53 12
54 36
55 18
56 24
57 16
58 40
59 40
60 12
61 12
62 42
63 20
64 24
65 22
66 46
67 46
68 16
69 42
70 20
71 20
72 32
73 32
74 24
75 52
76 18
77 40
78 24
79 24
80 36
81 28
82 58
83 58
84 16
85 60
86 30
87 36
88 32
89 32
90 48
91 20
92 66
93 32
94 44
95 24
96 70
97 70
98 24
99 72
100 36
Use este enlace para calcular la salida esperada para cualquier entrada. Además, aquíx <= 1000
se proporciona una lista de entradas y salidas para pastebin . (Generado con este programa Minkolang ).
Tablas de clasificación
Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.
Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:
## Language Name, N bytes
¿Dónde N
está el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:
## Perl, 43 + 2 (-p flag) = 45 bytes
También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento de la tabla de clasificación:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
fuente
Respuestas:
GS2 ,
1210 bytesEl código fuente usa la codificación CP437 . Pruébalo en línea!
Prueba de funcionamiento
Cómo funciona
fuente
Regex (NET),
122113 bytesSuponiendo que la entrada y la salida están en unario, y la salida se toma de la coincidencia principal de la expresión regular.
Desglose de la expresión regular:
^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))
calcula π̅ (x) y captura el resto de la cadena en el grupo de captura 6 para su afirmación en la segunda parte..*$
establece el puntero al final de la cadena para que tengamos el número enterox
en una dirección.(?<=^(\3+(.+.))(.*?(?>(.\4)?)))
coincide de derecha a izquierda y comprueba el número compuesto haciendo un bucle de x a 0.(.*?(?>(.\4)?))
es una "variable" que comienza desde 0 en la primera iteración y continúa desde el número en la iteración anterior y recorre hasta x. Como el número compuesto más pequeño es 4,(.\4)?
nunca falla si el grupo de captura 4 está disponible.^(\3+(.+.))
comprueba lo que queda por la "variable" de arriba (es decir,x - "variable"
si es un número compuesto).((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+
calcula φ (π̅ (x)), limitando las operaciones de izquierda a derecha con(?=\6$)
..*(?=\6$)
establece el puntero en la posición π̅ (x). Denotemos y = π̅ (x).(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))
coincide de derecha a izquierda y comprueba el primo relativo haciendo un bucle de (y - 1) a 0(.+?(?>\9?))
es una "variable" que comienza desde 1 en la primera iteración y continúa desde el número en la iteración anterior y recorre hasta y(?!(.+.)\8*(?=\6$)(?<=^\8+))
coincide de izquierda a derecha 1 y comprueba si la "variable" e y son primos relativos.(.+.)\8*(?=\6$)
elige un divisor de "variable" que es mayor que 1, y un efecto secundario es que tenemos el número entero y a la izquierda.(?<=^\8+)
comprueba si el divisor de "variable" es también el divisor de y.1 En .NET, la vista anticipada establece la dirección en LTR en lugar de seguir la dirección actual; mirar hacia atrás establece la dirección en RTL en lugar de invertir la dirección.
Prueba la expresión regular en RegexStorm .
La revisión 2 elimina los grupos que no capturan y usa grupos atómicos en lugar de sintaxis condicional.
fuente
J,
1514 bytesEste es un verbo tácito y monádico. Pruébalo en línea con J.js .
Cómo funciona
fuente
En serio , 27 bytes
¡Sí, le gané a CJam! Pruébalo en línea
Explicación (se
a
refiere a la parte superior de la pila, seb
refiere al segundo desde arriba):Nota: desde la publicación de esta respuesta, he agregado las funciones pi y phi a Seriously. Aquí hay una respuesta no competitiva con esas funciones:
Explicación (algunos comandos se desplazan para no superponerse a otros):
fuente
Julia,
5250 bytesEsto crea una función sin nombre que acepta un número entero y devuelve un número entero. Para llamarlo, asígnele un nombre, p. Ej.
f=x->...
.Sin golf:
fuente
sum
lugar decount
guardar un par de caracteres. Sin embargo, es un poco frustrante: la otra forma de contar los números primossum(isprime,1:x)
es exactamente la misma longitud queendof(primes(x))
.sum
falla por colecciones vacías mientrascount
devuelve 0. Porsum
lo tanto , no producirá el resultado deseado parax<4
.Mathematica, 24 bytes
fuente
PhiNotPi@#&
: 11 bytes: PPyth, 14 bytes
Demostración , verificador
Calculamos los compuestos usando un filtro simple, tomamos su longitud y lo guardamos en
J
. Luego, tomamos el mcd deJ
con cada número hastaJ
y contamos cuántos resultados equivalen a 1.fuente
Minkolang 0.11 , 12 bytes (NO competitivo)
Esta respuesta NO es competitiva. Implementé pi y phi como elementos integrados antes de publicar la pregunta, lo que me da una ventaja injusta. Publico esto solo para aquellos que estén interesados en el idioma.
Pruébalo aquí.
Explicación
fuente
CJam, 28 bytes
Pruébelo este violín en el intérprete CJam o verifique todos los casos de prueba a la vez .
Cómo funciona
fuente
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
. ¿Está bien?Pitón, 137
139fuente
range(n) if
y])) if
Retina , 48 bytes
Pruébalo en línea!
Explicación
Convierta la entrada a unario.
Cuente números compuestos que no sean mayores que la entrada contando con qué frecuencia podemos hacer coincidir una cadena que consta de al menos dos repeticiones de un factor de al menos 2.
Convierte a unario nuevamente.
Calcule φ contando a partir de cuántas posiciones no es posible encontrar un factor (de al menos 2) del sufijo de esa posición, que también es un factor del prefijo (si encontramos ese factor, entonces
i <= n
comparte un factor conn
Por lo tanto, no es coprime). Al.
final se asegura que no contamos cero (para lo cual no podemos encontrar un factor de al menos 2).fuente
Regex (.NET),
8886 bytesPruébalo en línea! (Como un programa de retina).
Utiliza la misma E / S que la respuesta de n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ , es decir, una entrada unaria y coincide con una subcadena de la longitud del resultado.
Es posible acortar esto aún más reemplazando uno o ambos grupos de equilibrio con referencias hacia adelante.
Alternativa al mismo número de bytes:
También hay algunas alternativas para la primera mitad, por ejemplo, usar una anticipación negativa en lugar de una positiva para los números compositivos, o también usar un condicional allí.
Explicación
Asumiré que tiene una comprensión básica de los grupos de equilibrio , pero en resumen, los grupos de captura en .NET son pilas (por lo que cada vez que reutiliza el grupo de captura, la nueva captura se coloca en la parte superior) y
(?<-x>...)
saca una captura de la pilax
. Eso es muy útil para contar cosas.fuente
PARI / GP, 27 bytes
fuente
Gelatina , no competidora
7 bytes Esta respuesta no es competitiva, ya que utiliza un lenguaje posterior al desafío.
Cómo funciona
fuente
Octava,
5251Editar: guardado 1 byte gracias a Thomas Kwa
Explicación:
fuente
PARI / GP, 35 bytes
fuente
SageMath 26 bytes
Funciona bien incluso para
n=0
yn=1
, gracias a la implementación de Sage.fuente
Jalea , 6 bytes
Pruébalo en línea!
Esta es una colaboración entre caird coinheringahhing y Mr. Xcoder en el chat
Explicación
fuente
Gaia , 5 bytes
Pruébalo en línea!
fuente
Ohm v2 , 7 bytes
Pruébalo en línea!
fuente
MATL , 9 bytes (no competitivos)
Esta respuesta no es competitiva, ya que el lenguaje es posterior al desafío.
Utiliza la versión (10.1.0) del lenguaje / compilador.
Pruébalo en línea!
Explicación
fuente
GAP, 33 bytes
Number(l,p)
cuenta cuántos elementos del
satisfacerp
. Para compensar el hecho de que 1 no es primo ni compuesto, tengo que restar de n uno más que el número de primos hasta n. En lugar de hacerlo-1
por dos bytes, comienzo la lista por -2 en lugar de 1 o 2, agregando así un número más que se considera primo porIsPrime
solo un byte adicional.fuente
Python 3.5 - 130 bytes
Si no es aceptable pasar la función como p (n, 0,0), entonces +3 bytes.
Esto aprovecha el hecho de que uso el teorema de Wilson para verificar si un número es compuesto y tengo que llamar al módulo matemático para la función factorial. Python 3.5 agregó una función gcd en el módulo matemático.
El primer bucle del código incrementará k en uno si el número es compuesto y aumentará en 0 de lo contrario. (Aunque el teorema de Wilson solo es válido para enteros mayores que 1, trata 1 como primo, por lo que nos permite explotar esto).
El segundo bucle se repetirá en el rango de número de compuestos e incrementará g solo cuando el valor de no pi y l sean primos conjuntos.
g es entonces el número de valores menor o igual que el número de números compuestos menor o igual que n.
fuente
Python 3 + sympy ,
5958 bytes* -1 byte reemplazando
compositepi(k)
conk+~primepi(k)
.Pruébalo en línea!
fuente
05AB1E ,
118 bytesPruébalo en línea!
Esto podría no ser competitivo: no puedo saber cuándo se creó 05AB1E.
Cómo funciona
fuente
Pyt , 6 bytes
Explicación:
Pruébalo en línea!
fuente
NARS APL, 38 bytes, 19 caracteres
13π es la función totient y 2π es la función prime count <= su argumento. Prueba
fuente
Agregar ++ , 21 bytes
Pruébalo en línea!
Cómo funciona
Esto simplemente implementaπ¯¯¯(n) φ(n) π¯¯¯(n) φ(n)
R
þP
þ
P
bL
1_
dR
Þ%
bL
G
!!
Sí, realmente quería probar el nuevo LaTex
fuente