Un número de Proth , llamado así por François Proth, es un número que se puede expresar como
N = k * 2^n + 1
Donde k
es un entero positivo impar y n
es un entero positivo tal que 2^n > k
. Usemos un ejemplo más concreto. Tome 3. 3 es un número de Proth porque se puede escribir como
(1 * 2^1) + 1
y 2^1 > 1
está satisfecho 5 También es un número de Proth porque se puede escribir como
(1 * 2^2) + 1
y 2^2 > 1
está satisfecho Sin embargo, 7 no es un número de Proth porque la única forma de escribirlo en el formulario N = k * 2^n + 1
es
(3 * 2^1) + 1
y 2^1 > 3
no está satisfecho
Su desafío es bastante simple: debe escribir un programa o función que, dado un entero positivo, determine si es un número de Proth o no. Puede ingresar datos en cualquier formato razonable, y debería generar un valor verdadero si es un número de Proth y un valor falso si no lo es. Si su idioma tiene funciones de "Detección de número de prototipo", puede usarlas.
Prueba IO
Aquí están los primeros 46 números de Proth hasta 1000. ( A080075 )
3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 289, 321, 353, 385, 417, 449, 481, 513, 545, 577, 609, 641, 673, 705, 737, 769, 801, 833, 865, 897, 929, 961, 993
Cualquier otra entrada válida debe dar un valor falso.
Como de costumbre, este es el código golf, por lo que se aplican las lagunas estándar, ¡y gana la respuesta más corta en bytes!
Nota al margen de la teoría de los números:
El primo más grande conocido que no es un Mersenne Prime es 19249 * 2^13018586 + 1
, ¡que también es un número Proth!
fuente
Python, 22 bytes
Este es un puerto de mi respuesta Jelly . Pruébalo en Ideone .
Cómo funciona
Sea j un número estrictamente positivo. j + 1 alterna todos los bits del conjunto final de j y el bit adyacente no establecido. Por ejemplo, 10011 2 + 1 = 10100 2 .
Dado que ~ j = - (j + 1) = -j - 1 , -j = ~ j + 1 , entonces -n aplica lo anterior al NOT bit a bit de j (que alterna todos los bits), alternando todos los bits antes del último 1 .
Al tomar j & -j - el AND bit a bit de j y -j - todos los bits antes y después del último bit establecido se anulan (ya que son desiguales en j y -j ), produciendo así la mayor potencia de 2 que divide j uniformemente.
Para la entrada N , queremos aplicar lo anterior a N - 1 para encontrar 2 n , la potencia más alta de 2 que divide N - 1 . Si m = N - 1 , -m = - (N - 1) = 1 - N , entonces (N - 1) y (1 - N) rinden 2 n .
Todo lo que queda por probar es si 2 n > k . Si k> 0 , esto es cierto si y sólo si (2 n ) 2 > k2 n , lo cual es cierto en sí si y sólo si (2 n ) 2 ≥ k2 n + 1 = N .
Finalmente, si (2 n ) 2 = N = k2 n + 1 , 2 n debe ser impar ( 1 ) para que las paridades de ambos lados puedan coincidir, lo que implica que k = 0 y N = 1 . En este caso (N - 1) y (1 - n) = 0 y 0 = 0 y ((N - 1) y (1 - N)) 2 = 0 <1 = N .
Por lo tanto, ((N - 1) y (1 - N)) 2 > N es verdadero si y solo si N es un número de Proth.
Ignorando las imprecisiones de coma flotante, esto es equivalente al código
N-1&1-N>N**.5
en la implementación.fuente
Python 2, 23 bytes
fuente
Mathematica,
5048454038353129 bytesMathematica generalmente apesta cuando se trata de golf de código, pero a veces hay una función incorporada que hace que las cosas se vean realmente bien.
Una prueba:
Editar: en realidad, si le robo la idea AND AND de Dennis , puedo reducirlo a
232220 bytes.Mathematica,
232220 bytes (gracias A Simmons )fuente
g=
, ¡una función pura está bien!Select[Range@1000,f]
.05AB1E ,
1410 bytes¡Gracias a Emigna por guardar 4 bytes!
Código:
Utiliza la codificación CP-1252 . Pruébalo en línea! .
Explicación:
Para la explicación, usemos el número 241 . Primero disminuimos el número en uno con
<
. Eso da como resultado 240 . Ahora, calculamos los factores primos (con duplicados) usandoÒ
. Los factores primos son:Los dividimos en dos partes. Usando
2Q·0K
, obtenemos la lista de dos:Con
®2K
, obtenemos la lista de los números restantes:Finalmente, tome el producto de ambos.
[2, 2, 2, 2]
resultados en 16 . El producto de los[3, 5]
resultados en 15 .Este caso de prueba es verdadero desde 16 > 15 .
fuente
<©Ó¬oD®s/›
o<DÓ0èoDŠ/›
por 10.Cerebro-Flak ,
460350270266264188176 bytesPruébalo en línea!
Explicación
El programa pasa por potencias de dos y cuatro hasta que encuentra una potencia de dos mayor que N-1. Cuando lo encuentra, verifica la divisibilidad de N-1 por la potencia de dos usando el módulo y genera el resultado
Este programa no es de pila limpia. Si agrega 4 bytes adicionales, puede hacer que se apile limpiamente:
fuente
MATL , 9 bytes
La verdad es la salida
1
. Falsy es0
o salida vacía. (Las únicas entradas que producen una salida vacía son1
y2
; el resto produce una0
o1
).Pruébalo en línea!
Explicación
Dejar x denotar la entrada. Sea y la mayor potencia de 2 que divide x −1, y z = ( x −1) / y . Tenga en cuenta que z es automáticamente impar. Entonces x es un número de Proth si y solo si y > z , o de manera equivalente si y 2 > x −1.
fuente
Brachylog , 28 bytes
Pruébalo en línea!
Verifique todas las cajas de prueba a la vez. (Ligeramente modificado.)
Explicación
Brachylog, al ser un derivado de Prolog, es muy bueno para probar cosas.
Aquí, probamos estas cosas:
fuente
Haskell,
5546 bytesEditar: Gracias a nimi, ahora 46 bytes
fuente
sum[1| ... ]
. Aquí podemos ir más allá y pasar la prueba de la igualdad frente al|
y consulte conor
si alguna de ellas es cierta:f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k]
.ECMAScript Regex,
484341 bytesLas expresiones regulares de Neil y H.PWiz (ambas también sabor ECMAScript) son hermosas por derecho propio. Hay otra manera de hacerlo, que por una coincidencia bastante limpio fue de 1 byte de más de Neil, y ahora con el golf sugerido por H.PWiz (gracias!), Es de 1 byte
mása menos de H.PWiz de.Advertencia: pesar del pequeño tamaño de esta expresión regular, contiene un spoiler importante . Recomiendo encarecidamente aprender cómo resolver problemas matemáticos unarios en expresiones regulares ECMAScript descubriendo las ideas matemáticas iniciales de forma independiente. 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.
Entonces, esta expresión regular funciona de manera bastante simple: comienza restando uno. Luego encuentra el factor impar más grande, k . Luego dividimos por k (usando el algoritmo de división explicado brevemente en un párrafo etiquetado con spoiler de mis números factoriales regex post ). Escurridizos hacemos una afirmación simultánea de que el cociente resultante es mayor que k . Si la división coincide, tenemos un número de Proth; si no, no lo hacemos.
Pude eliminar 2 bytes de esta expresión regular (43 → 41) usando un truco encontrado por Grimy que puede acortar aún más la división en el caso de que el cociente sea mayor o igual que el divisor.
Pruébalo en línea!
fuente
Julia, 16 bytes
¡Créditos a @Dennis por la respuesta y algunos consejos de golf!
fuente
&
tiene la misma precedencia que*
.-~-x
lugar de(1-x)
. Además, hay en√x
lugar dex^.5
, pero no guarda ningún byte.R,
5250 bytesEl programa comienza dividiendo
N-1
(llamado aquíP
yx
) por el2
mayor tiempo posible para encontrar la2^n
parte de la ecuación, dejandok=(N-1)/2^n
y luego calcula sik
es inferior o no2^n
, utilizando el hecho de que2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x
fuente
P=
al principio, cambiar el final2^n>x
y guardar como 5 o 6 bytesRegex (ECMAScript),
4038 bytes-2 bytes gracias a Deadcode
Pruébalo en línea!
Versión comentada:
fuente
^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)
( Pruébelo en línea )J, 10 bytes
Basado en @Dennis 'bitwise solución .
Toma una entrada
n
y devuelve 1 si es el número de Proth más 0.Uso
Explicación
fuente
AND
. ¡guay!Retina 0.8.2 , 47 bytes
Pruébalo en línea! Explicación: dado un número de Prothk ⋅ 2norte+ 1 , puedes derivar dos nuevos números de Proth ( 2 k ± 1 ) ⋅ 2n + 1+ 1 . Podemos ejecutar esto en reversa hasta que obtengamos un número de Proth dondek = 1 . Esto se realiza fácilmente transformando la representación binaria.
Convierte a unario.
Convierte a binario.
Ejecute repetidamente la fórmula de generación de Proth en reversa.
Haga coincidir el caso base de la fórmula de generación Proth.
Editar: Creo que en realidad es posible hacer coincidir un número de Proth directamente con un número unario con una sola expresión regular. Esto actualmente me lleva 47 bytes, 7 bytes más que mi código Retina actual para verificar si un número unario es un número de Proth:
fuente
ECMAScript Regex, 42 bytes
Pruébalo en línea!(Usando retina)
Esencialmente resto 1, divido por el número impar más grande posible
k
, luego verifico que al menosk+1
sobra.Resulta que mi expresión regular es muy similar a la que Neil da al final de su respuesta . Yo uso en
x(xx)*
lugar de(x*)\2x
. Y uso un método más corto para verificark < 2^n
fuente
(\3\3)*)$
a(\3\3)*$)
$=
y$.=
. Se puede mejorar aún mejor .Brain-Flak , 128 bytes
Pruébalo en línea!
Utilicé un algoritmo muy diferente que la solución más antigua de Brain-Flak .
Básicamente, divido por 2 (redondeando) hasta que llegue a un número par. Luego solo comparo el resultado de la última división con los dos con la potencia del número de veces que dividí.
Explicación:
fuente
Arce, 100 bytes (incluidos espacios)
Muy bien espaciados para la lectura:
La misma idea que varias otras; divida X por 2 hasta que X ya no sea divisible por 2, luego verifique los criterios 2 ^ n> x.
fuente
Java 1.7,
4943 bytesOtros 6 bytes el polvo gracias a @charlie.
¡Intentalo!(ideona)
Dos formas, igualmente largas. Como con la mayoría de las respuestas aquí, los créditos van a @Dennis, por supuesto, para la expresión.Tomando la raíz del lado derecho de la expresión:
Aplicando el poder de dos al lado izquierdo de la expresión:
Puede eliminar un solo byte si se permite que un valor numérico positivo represente 'verdadero' y un valor negativo 'falso':
Desafortunadamente, debido a la "Conversión primitiva estrecha", uno no puede simplemente escribir esto en Java y obtener resultados correctos:
Y cualquier intento de ampliar 'p' conducirá a un error de compilación porque los operadores bit a bit no son compatibles con, por ejemplo, flotantes o dobles :(fuente
boolean f(int p){return Math.sqrt(p--)<(p&-p);}
boolean g(int p){return p--<(p&-p)*(p&-p);}
Math.*
llamadas; simplemente no podía entender cómo! ¡Gracias!Hy , 37 bytes
Pruébalo en línea!
Puerto de la respuesta de @Dennis.
fuente
C (gcc) , 29
30bytesPruébalo en línea!
fuente
Japt ,
12109 bytesPruébalo en línea!
Port of Dennis 'Jelly responde de nuevo. - 1 gracias a @Shaggy.
fuente
-1
puede serÉ
.Cjam, 11 bytes
Como muchos de nosotros, aprovechamos la excelente solución de Dennis:
Pruébalo en línea
fuente
C (137 bytes)
Solo vine a leer las respuestas después de que lo intenté.
Considerando
N=k*2^n+1
con el condicional dek<2^n
(k=1,3,5..
yn=1,2,3..
Con
n=1
tenemos unok
disponible para probar. A medida que aumentamosn
, obtenemos algunos másk's
para probar así:n = 1; k = 1
n = 2; k = 1 k = 3
n = 3; k = 1 k = 3 k = 5 k = 7
...
Iteración a través de las posibilidades que podemos estar seguros de N no es un número Prouth si por un hecho
n
lak=1
número obtenido es mayor que N y ninguna otra iteración fue una coincidencia.Así que mi código básicamente "fuerza bruta" su camino para encontrar N.
Después de leer las otras respuestas y darse cuenta de que puede factorizar N-1 con 2 para encontrar
n
y luego condicionark<2^n
, creo que mi código podría ser más pequeño y más eficiente usando este método.¡Valió la pena intentarlo!
Probó todos los números dados y algunos números "no Prouth". La función devuelve 1 si el número es un número de Prouth y 0 si no lo es.
fuente
Javascript ES7, 16 bytes
El puerto de mi respuesta de Julia, que es un puerto de la respuesta de @ Dennis's Jelly.
¡Gracias @Charlie por 2 bytes guardados!
fuente
n=x=>x-1&1-x>x**.5; n(3)
me da0
(en realidad me da 0 independientemente de la entrada)n=x=>x-1&1-x>Math.pow(x,0.5); n(3)
(x-1&1-x)
ya que sin ella, la prioridad del operador es en realidad:(x-1)&((1-x)>x**.5)
x=>x--**.5<(x&-x)
ox=>x**.5<(--x&-x)
C # (.NET Core) , 17 bytes
Pruébalo en línea!
La respuesta C del puerto de MegaTom .
Intenté una solución basada en LINQ, pero fue demasiado buena.
fuente
tinta , 60 bytes
Pruébalo en línea!
Basado en la respuesta de Maple de @ DSkoog : no fue el primero de su tipo en publicarse, pero fue el primero de su tipo que vi.
Sin golf
fuente
Código de máquina x86, 15 bytes
Estos bytes definen una función que toma el argumento de entrada (un entero sin signo) en el
EDI
registro, siguiendo la convención de llamada estándar del Sistema V para sistemas x86, y devuelve el resultado en elEAX
registro, como todas las convenciones de llamada x86.En mnemotecnia de ensamblador:
Pruébalo en línea!
Es una solución bastante sencilla, y conceptualmente similar a la versión C de MegaTom . De hecho, podría escribir esto en C como algo parecido a lo siguiente:
pero el código de máquina anterior está mejor desarrollado que el que obtendrá de un compilador de C, incluso cuando está configurado para optimizar el tamaño.
El único "truco" aquí es devolver -1 como un valor "verdadero" y 0 como un valor "falso". Este truco permite el uso de la
SBB
instrucción de 2 bytes en lugar de laSETB
instrucción de 3 bytes .fuente