Hace un tiempo, eché un vistazo a la factorización prima de 27000:
27000 = 2 3 × 3 3 × 5 3
Hay dos cosas especiales al respecto:
- consecutiva de alto riesgo : Los números primos son consecutivas: 2 es la primera de primera, 3 es el segundo primo, 5 es el primer tercio.
- constante-exponente : el exponente es el mismo para cada primo (siempre 3)
Expresado matemáticamente:
Un número entero x es un número primo consecutivo / exponente constante si existen enteros estrictamente positivos n , k , m tal que x = p n m × p n +1 m × ... × p n + k m , donde p j es el j -ésimo primer
Su tarea es probar si un entero positivo cumple estas condiciones.
Entrada:
Un entero positivo> 1, en cualquier forma razonable.
Salida:
Uno de los dos valores, al menos uno de los cuales tiene que ser constante, lo que indica si la entrada es un número primo consecutivo / exponente constante.
Casos de borde:
- los números primos son verdaderos, ya que la factorización para primer p es p 1
- otros números que se pueden escribir como p m donde p es primo también son verdaderos.
Reglas:
- Se aplican lagunas estándar.
- No se preocupe por el desbordamiento de enteros, pero los números hasta 255 deben funcionar.
- El código más corto en bytes gana.
Casos de prueba:
Verdad:
2
3
4
5
6
7
8
9
11
13
15
27000
456533
Falsy
10
12
14
72
10000000
Aquí hay un script de Python que genera algunos casos de prueba.
x = Pn^m
parte. Supongo que querías decir que Pn es elRespuestas:
05AB1E , 4 bytes
Pruébalo en línea!
Explicación
fuente
ÎÓKË
es todo lo que puedo pensar aparte de esto, agradable ... Estaba pensandoß
pero hace lo contrario de lo que pensaba.Regex (ECMAScript),
276205201193189 bytesComparar las multiplicidades (exponentes) de diferentes factores primos es un problema interesante para resolver con la expresión regular ECMAScript: la falta de referencias posteriores que persisten a través de iteraciones de un bucle hace que sea un desafío contar cualquier cosa. Incluso si es posible contar el rasgo numérico en cuestión, a menudo un enfoque más indirecto mejora el golf.
Al igual que con mis otras publicaciones de expresiones regulares ECMA, daré una advertencia de spoiler: recomiendo aprender a resolver problemas matemáticos unarios en expresiones regulares ECMAScript. Ha sido un viaje fascinante para mí, y no quiero estropearlo para cualquiera que quiera probarlo ellos mismos, especialmente aquellos interesados en la teoría de números. Consulte esta publicación anterior para obtener una lista de problemas recomendados etiquetados consecutivamente con spoilers para resolver uno por uno.
Así que no sigas leyendo si no quieres que se te estropee un poco de magia regex unaria avanzada . Si desea intentar descubrir esta magia usted mismo, le recomiendo comenzar resolviendo algunos problemas en la expresión regular de ECMAScript como se describe en la publicación vinculada anteriormente.
La carga útil principal de una expresión regular que desarrollé previamente resultó ser muy aplicable a este desafío. Esa es la expresión regular que encuentra el (los) primo (s) de mayor multiplicidad . Mi primera solución para eso fue muy larga, y luego lo jugué por etapas, primero lo reescribí para usar el lookahead molecular , y luego lo volví a convertir al ECMAScript simple usando una técnica avanzada para evitar la falta de lookahead molecular , y luego jugando golf para que sea mucho más pequeño que la solución ECMAScript original.
La parte de esa expresión regular que se aplica a este problema es el primer paso, que encuentra Q, el factor más pequeño de N que comparte todos sus factores primos. Una vez que tenemos este número, todo lo que tenemos que hacer para demostrar que N es un "número de exponente constante" es dividir N entre Q hasta que no podamos más; Si el resultado es 1, todos los primos son de igual multiplicidad.
Después de enviar una respuesta usando mi algoritmo previamente desarrollado para encontrar Q, me di cuenta de que podría calcularse de una manera completamente diferente: encontrar el factor libre de cuadrados más grande de N (usando el mismo algoritmo que mi expresión regular de números de Carmichael ). Resulta que esto no plantea ninguna dificultad * en términos de evitar la falta de anticipación molecular y de retroceso de longitud variable (no es necesario incorporar la técnica avanzada utilizada anteriormente), ¡y es 64 bytes más corto! Además, elimina la complejidad de tratar el N sin cuadrados y el N principal como diferentes casos especiales, eliminando otros 7 bytes de esta solución.
(Todavía quedan otros problemas que requieren la técnica avanzada utilizada anteriormente para reducir el cálculo de Q, pero actualmente ninguno de ellos está representado por mis publicaciones PPCG).
Puse la prueba de multiplicidad antes de la prueba de primos consecutivos porque esta última es mucho más lenta; poner pruebas que pueden fallar más rápidamente primero hace que la expresión regular sea más rápida para una entrada distribuida uniformemente. También es mejor el golf para ponerlo primero, porque usa más referencias inversas (lo que costaría más si fueran de dos dígitos).
Pude eliminar 4 bytes de esta expresión regular (193 → 189) usando un truco encontrado por Grimy que puede acortar aún más la división en el caso de que se garantice que el cociente sea mayor o igual que el divisor.
^(?=(|(x+)\2*(?=\2$))((?=(xx+?)\4*$)(?=(x+)(\5+$))\6(?!\4*$))*x$)(?=.*$\2|((?=((x*)(?=\2\9+$)x)(\8*$))\10)*x$)(?!(((x+)(?=\13+$)(x+))(?!\12+$)(x+))\11*(?=\11$)(?!(\15\14?)?((xx+)\18+|x?)$))
Pruébalo en línea!
* Todavía es más limpio con anticipación molecular, sin ningún caso especial para que N esté libre de cuadrados. Esto deja caer 6 bytes, produciendo una solución de
195187183 bytes :^(?=(?*(x+))\1*(?=\1$)((?=(xx+?)\3*$)(?=(x+)(\4+$))\5(?!\3*$))*x$)(?=((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$)(?!(((x+)(?=\12+$)(x+))(?!\11+$)(x+))\10*(?=\10$)(?!(\14\13?)?((xx+)\17+|x?)$))
Aquí está portado a lookbehind de longitud variable:
Expresiones regulares (ECMAScript 2018),
198195194186182 bytes^(?=(x+)(?=\1*$)(?<=^x((?<!^\5*)\3(?<=(^\4+)(x+))(?<=^\5*(x+?x)))*))((?=((x*)(?=\1\8+$)x)(\7*$))\9)*x$(?<!(?!(\14\16?)?((xx+)\12+|x?)$)(?<=^\13+)((x+)(?<!^\15+)((x+)(?<=^\17+)(x+))))
Pruébalo en línea!
fuente
.*$\2
con\2^
^(?=(|(x+)\2*(?=\2$))(((?=(xx+?)\5*$)(?=(x+)(\6+$))\7(?!\5*$))*x$))(?!(((xx+)(?=\10+$)(x+))(?!\9+$)(x+))\8*(?=\8$)(?!(\12\11?)?(xx+)\14+$))((?=((x*)(?=\2\17+$)x)(\16*$))\19)*\3$
Jalea ,
1365 bytesPruébalo en línea!
Todavía superado ... (gracias Erik por -1 byte)
Explicación
fuente
œl
->t
. No hay razón para que los ceros finales estén presentes en la salida de ÆE.JavaScript (ES6), 87 bytes
Devuelve 0 para verdadero o un entero distinto de cero para falso.
Pruébalo en línea!
Comentado
fuente
j||i
ai
. Ahora produce muchos falsos positivos.CJam ,
3029 bytesPruébalo en línea!
Mi primera respuesta después de un descanso de casi 2 (!) Años, por lo que probablemente pueda jugar más. Este es un bloque que toma la entrada como un entero (también se puede asignar para matrices de enteros).
Explicación
fuente
Stax ,
56 bytesEjecutar y depurarlo
Desempaquetado, sin golf y comentado, se ve así.
Editar:
esto no funcionaAhora funciona.512
. Lo pensaré un poco y, con suerte, una solución más tarde.fuente
Stax , 9 bytes
1 es verdadero, 0 es falso
Ejecutar y depurarlo
Explicación
Probablemente se pueda jugar más al golf, pero cubre los casos que me faltaban en la última solución.
fuente
MATL ,
12 1110 bytes¡Pruébalo en MATL Online!
Gracias a Luis Mendo por la parte de eliminar ceros a la izquierda. También señaló que se permite intercambiar valores de verdad, por lo que esto devuelve 0 para los números que satisfacen los requisitos de desafío y cualquier valor positivo de lo contrario.
Grosso Modo, esto genera los exponentes de la factorización prima secuencial, elimina los ceros a la izquierda y calcula la desviación estándar.
fuente
0iYFhdz
funciona para 7 bytes: anteponer un 0 a los exponentes de la factorización secuencial, diferencias consecutivas, número de ceros distintos. El resultado es1
si la entrada satisface el requisitoJava 10
223191178176168 bytesVuelve
1
como veraz y>=2
como falsey.Pruébalo en línea.
Explicación:
Algunas entradas de ejemplo:
n=15
:1
para el primer primo 2 (porque 15 no es divisible por 2).1
a0
tan pronto como estemos en el número 3. Como 15 es divisible por 3, sen
convierte en 5 (15/3 1 ), y el Conjunto se convierte en[] → [1]
.n
convierte en 1 (5/5 1 ), y el Conjunto permanece igual ([1] → [1]
).n=1
, entonces detenemos el bucle externo. El Set ([1]
) solo contiene un elemento, el1
de los dos primos adyacentes 3 y 5, por lo que devolvemos verdadero.n=14
:1
a0
para el primer primo 2 (porque 14 es divisible por 2).n
se convierte en 7 (14/2 1 ), y el Set se convierte en[] → [1]
.n
permanece igual y el Conjunto se convierte[1] → [1,0]
.n
sigue siendo el mismo y el Conjunto sigue siendo el mismo ([1,0] → [1,0]
).n
convierte en 1 (7/7 1 ), y el Conjunto permanece igual ([1,0] → [1,0]
).n=1
, entonces detenemos el bucle externo. El Set ([1,0]
) contiene dos elementos, el1
de los primos no adyacentes 2 y 7, y el0
de los primos 3 y 5, por lo que devolvemos falso.n=72
:1
a0
para el primer primo 2, porque 72 es divisible por 2 (varias veces). Entonces sen
convierte en 9 (72/2 3 ), y el Set se convierte en[] → [3]
.n
convierte en 1 (9/3 2 ), y el Conjunto se convierte en[3] → [3,2]
.n=1
, entonces detenemos el bucle externo. El Set ([3,2]
) contiene dos elementos,3
from from prime 2 y2
from from prime 3, por lo que devolvemos false.fuente
<2
y devolver un int (especifique que devuelve 1 para la verdad).1
es veraz y2
o más alto es falsey. Gracias.J , 16 bytes
¡Muchas gracias a FrownyFrog por -8 bytes!
Pruébalo en línea!
Mi vieja solución:
J , 24 bytes
Pruébalo en línea!
Explicación:
_&q:
exponentes primos{.@I.}.]
elimina los ceros iniciales al encontrar el primer elemento distinto de cero:1=[:#@~.
prueba si todos los números restantes son iguales:fuente
Casco , 11 bytes
Pruébalo en línea!
Emite 0 si no es un número primo consecutivo / exponente constante.
fuente
MATL , 7 bytes
El resultado es
1
si la entrada cumple el requisito.Pruébalo en línea! O verificar todos los casos de prueba
Explicación
fuente
Octava , 67 bytes
Pruébalo en línea!
Creo que esta es la única solución que usa un histograma.
Explicación:
Esto hace un histograma, donde la variable a contar son los factores de la entrada y se colocan en los contenedores.
primes(x)
, que son todos primos menores que la entrada. Luego encontramos la ubicación de los factores primos, tomamos la diferencia entre cada uno de los índices y restamos uno. Si hay elementos que no son cero (es decir, la diferencia de los índices de los números primos no es 1), esto dará como resultado un valor falso, de lo contrario devolverá un valor verdadero.Luego verificamos que todos los elementos distintos de cero en el histograma son iguales al elemento máximo. Si hay valores que no son iguales, esto dará como resultado un valor falso, de lo contrario devolverá un valor verdadero.
Si ambos bloques son verdaderos, ¡entonces nuestra entrada es un número de exponente constante primo consecutivo!
fuente
APL (Dyalog Extended) , 28 bytes
Pruébalo en línea!
Cómo:
fuente
Wolfram Language (Mathematica) , 65 bytes
Pruébalo en línea!
fuente
Pari / GP , 63 bytes
Pruébalo en línea!
fuente
J , 14 bytes
1 en la salida indica exponente constante consecutivo.
Pruébalo en línea!
fuente
Limpio , 127 bytes
Pruébalo en línea!
Define la función
? :: Int -> Bool
usando$ :: Int -> [Int]
para factorizar y@ :: Int -> Bool
verificar la primalidad.fuente
APL (NARS) 41 caracteres, 82 bytes
{π⍵} es la factorización de función del argumento ⍵ en la lista de factores primos (repita si un primo aparece más tiempo);
{1π⍵} es la función next prime (tenga en cuenta que en este caso su argumento no es un escalar sino una matriz de enteros). prueba:
fuente