¿Es un número de Proth?

37

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 kes un entero positivo impar y nes 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 > 1está satisfecho 5 También es un número de Proth porque se puede escribir como

(1 * 2^2) + 1

y 2^2 > 1está satisfecho Sin embargo, 7 no es un número de Proth porque la única forma de escribirlo en el formulario N = k * 2^n + 1es

(3 * 2^1) + 1

y 2^1 > 3no 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!

DJMcMayhem
fuente

Respuestas:

41

Jalea , 5 bytes

’&C²>

Pruébalo en línea! o verificar todos los casos de prueba .

Fondo

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.

Cómo funciona

’&C²>  Main link. Argument: N

’      Decrement; yield N - 1.
  C    Complement; yield 1 - N.
 &     Take the bitwise AND of both results.
   ²   Square the bitwise AND.
    >  Compare the square to N.
Dennis
fuente
woah eso es increíble
don brillante
46

Python, 22 bytes

lambda N:N-1&1-N>N**.5

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**.5en la implementación.

Dennis
fuente
23
Frecuenta Math.SE, y mis ojos realmente desean un hermoso LaTeX en este sitio en lugar de parecer un sitio de los 90 ...
qwr
Este es mi favorito.
Qix
9

Python 2, 23 bytes

lambda n:(~-n&1-n)**2>n
Feersum
fuente
9

Mathematica, 50 48 45 40 38 35 31 29 bytes

Mathematica 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.

1<#<4^IntegerExponent[#-1,2]&

Una prueba:

Reap[Do[If[f[i],Sow[i]],{i,1,1000}]][[2,1]]

{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}

Editar: en realidad, si le robo la idea AND AND de Dennis , puedo reducirlo a 23 22 20 bytes.

Mathematica, 23 22 20 bytes (gracias A Simmons )

BitAnd[#-1,1-#]^2>#&
Michael Lee
fuente
2
¡Bienvenido a Programming Puzzles y Code Golf! :)
Adnan
1
No es necesario comenzar g=, ¡una función pura está bien!
Un Simmons
Oh dulce. Lo arregló ahora.
Michael Lee
Por cierto, su prueba puede simplificarse significativamente Select[Range@1000,f].
numbermaniac
8

05AB1E , 14 10 bytes

¡Gracias a Emigna por guardar 4 bytes!

Código:

<©Ó¬oD®s/›

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:

[2, 2, 2, 2, 3, 5]

Los dividimos en dos partes. Usando 2Q·0K, obtenemos la lista de dos:

[2, 2, 2, 2]

Con ®2K, obtenemos la lista de los números restantes:

[3, 5]

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 .

Adnan
fuente
<©Ó¬oD®s/›o <DÓ0èoDŠ/›por 10.
Emigna
@Emigna ¡Eso es genial! Gracias :).
Adnan
7

Cerebro-Flak , 460 350 270 266 264 188 176 bytes

Prué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

({}[()])      #Subtract one from input
(((<>())))    #Put three ones on the other stack
{
 {}           #Pop the crap off the top
 ([(
  ((({}<(({}){})>){}){}) #Multiply the top by four and the bottom by two
  <>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{} #Check if the power of four is greater than N-1
}
(<{}{}>) #Remove the power of 4
<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>) #Modulo N-1 by the power of two

Este programa no es de pila limpia. Si agrega 4 bytes adicionales, puede hacer que se apile limpiamente:

({}[()])(((<>()))){{}([(((({}<(({}){})>){}){})<>[({})(())])](<>)){({}())<>}{}<>{}{}<>(({})){{}{}<>(<(())>)}{}}(<{}{}>)<>{({}[()])<>(({}()[({})])){{}(<({}({}))>)}{}<>}{}<>({}<{}><>)
Asistente de trigo
fuente
5

MATL , 9 bytes

qtYF1)EW<

La verdad es la salida 1. Falsy es 0o salida vacía. (Las únicas entradas que producen una salida vacía son 1y 2; el resto produce una 0o 1).

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.

q    % Input x implicitly. Subtract 1
t    % Duplicate
YF   % Exponents of prime factorization of x-1
1)   % First entry: exponent of 2. Errors for x equal to 1 or 2
E    % Duplicate
W    % 2 raised to that. This is y squared
<    % Is x-1 less than y squared? Implicitly display
Luis Mendo
fuente
5

Brachylog , 28 bytes

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

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:

>N>0,2:N^P:K*+?,P>K:2%1,N:K=

>N>0                           input > N > 0
     2:N^P                     2^N = P
         P:K*+?                P*K+1 = input
                P>K            P > K
                  K:2%1        K%2 = 1
                        N:K=   [N:K] has a solution
Monja permeable
fuente
5

Haskell, 55 46 bytes

f x=length [x|k<-[1,3..x],n<-[1..x],k*2^n+1==x,2^n>k]>0

Editar: Gracias a nimi, ahora 46 bytes

f x=or[k*2^n+1==x|k<-[1,3..x],n<-[1..x],2^n>k]
X88B88
fuente
44
¡Bienvenido a Programming Puzzles & Code Golf!
Dennis
¡Gracias hombre! He estado al acecho aquí por un tiempo. Gran fan por cierto, la gelatina es súper genial. Ojalá pudiera aprender pero, por desgracia, no entiendo realmente
X88B88
2
Un consejo general: si solo está interesado en la longitud de una lista creada por una comprensión, puede usarla sum[1| ... ]. Aquí podemos ir más allá y pasar la prueba de la igualdad frente al |y consulte con orsi alguna de ellas es cierta: f x=or[k*2^n+1==x|k<-...,n<-...,2^n>k].
nimi
Guau. Grandes consejos Definitivamente lo revisaré.
X88B88
2
Si estás interesado en aprender Jelly, mira la wiki o únete a la sala Jelly .
Dennis
5

ECMAScript Regex, 48 43 41 bytes

Las 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ás a 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.

^x(?=(x(xx)*)\1*$)((\1x*)(?=\1\4*$)x)\3*$

Pruébalo en línea!


 # Match Proth numbers in the domain ^x*$
 ^
 x                         # tail = tail - 1
 (?=(x(xx)*)\1*$)          # \1 = largest odd factor of tail
 
 # Calculate tail / \1, but require that the quotient, \3, be > \1
 # (and the quotient is implicitly a power of 2, because the divisor
 # is the largest odd factor).
 (                         # \3 = tail / \1, asserting that \3 > \1
     (\1x*)                # \4 = \3-1
     (?=\1\4*$)            # We can skip the test for divisibility by \1-1
                           # (and avoid capturing it) because we've already
                           # asserted that the quotient is larger than the
                           # divisor.
     x
 )
 \3*$
 

Código muerto
fuente
1
O_o wow, solo 48 bytes
solo ASCII
Neil's es más similar al mío que al de Dennis
H.PWiz
4

Julia, 16 bytes

!x=~-x&-~-x>x^.5

¡Créditos a @Dennis por la respuesta y algunos consejos de golf!

Mama Fun Roll
fuente
Eso no funciona En Julia, &tiene la misma precedencia que *.
Dennis
1
Correcto. Solucionado: PI realmente debería probar mi código.
Mama Fun Roll
2
Puedes usar en -~-xlugar de (1-x). Además, hay en √xlugar de x^.5, pero no guarda ningún byte.
Dennis
4

R, 52 50 bytes

x=scan()-1;n=0;while(!x%%2){x=x/2;n=n+1};2^(2*n)>x

El programa comienza dividiendo N-1(llamado aquí Py x) por el 2mayor tiempo posible para encontrar la 2^nparte de la ecuación, dejandok=(N-1)/2^n y luego calcula si kes inferior o no 2^n, utilizando el hecho de que2^n>x/2^n <=> (2^n)²>x <=> 2^2n>x

Frédéric
fuente
1
Puede extraer el P=al principio, cambiar el final 2^n>xy guardar como 5 o 6 bytes
user5957401
4

Regex (ECMAScript), 40 38 bytes

-2 bytes gracias a Deadcode

^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)

Pruébalo en línea!

Versión comentada:

# Subtract 1 from the input N
^x

# Assert N is even.
# Capture \1 = biggest power of 2 that divides N.
# Capture \2 = 2.
(?=((xx)+?)(\1\1)*$)

# Assert no odd number > \1 divides N
(?!(\1x\2*)\4*$)
Mugriento
fuente
Wow, esto es muy bueno. ¡Muchas maneras diferentes de resolver este problema!
Código muerto
1
38 bytes: ^x(?=((xx)+?)(\1\1)*$)(?!(\1x\2*)\4*$)( Pruébelo en línea )
Deadcode
2

J, 10 bytes

%:<<:AND-.

Basado en @Dennis 'bitwise solución .

Toma una entrada n y devuelve 1 si es el número de Proth más 0.

Uso

   f =: %:<<:AND-.
   f 16
0
   f 17
1
   (#~f"0) >: i. 100  NB. Filter the numbers [1, 100]
3 5 9 13 17 25 33 41 49 57 65 81 97

Explicación

%:<<:AND-.  Input: n
        -.  Complement. Compute 1-n
   <:       Decrement. Compute n-1
     AND    Bitwise-and between 1-n and n-1
%:          Square root of n
  <         Compare sqrt(n) < ((1-n) & (n-1))
millas
fuente
Huh No sabía acerca AND. ¡guay!
Conor O'Brien
2

Retina 0.8.2 , 47 bytes

\d+
$*
+`(1+)\1
$+0
01
1
+`.10(0*1)$
1$1
^10*1$

Pruébalo en línea! Explicación: dado un número de Prothk·2norte+1, puedes derivar dos nuevos números de Proth (2k±1)·2norte+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.

\d+
$*

Convierte a unario.

+`(1+)\1
$+0
01
1

Convierte a binario.

+`.10(0*1)$
1$1

Ejecute repetidamente la fórmula de generación de Proth en reversa.

^10*1$

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:

^.(?=(.+?)(\1\1)*$)(?=((.*)\4.)\3*$).*(?!\1)\3$
Neil
fuente
2

ECMAScript Regex, 42 bytes

^x(?=(x(xx)*)\1*$)(?=(x+?)((\3\3)*$))\4\1x

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

H.PWiz
fuente
Wow, esto es asombroso! Muy bien hecho. Tenga en cuenta que puede hacerlo un poco más rápido cambiando (\3\3)*)$a(\3\3)*$)
Deadcode
Buen trabajo con ese código Retina. No sabía sobre $=y $.=. Se puede mejorar aún mejor .
Código muerto el
2
@Deadcode Si vas a seleccionar el encabezado y el pie de página, entonces tienes algunas mejoras adicionales .
Neil
@Neil Parece un buen golf, pero desafortunadamente parece tener un error. Prueba con números individuales . Ellos no trabajan
Código muerto el
1
@Deadcode Lo siento, no me había dado cuenta de que los números individuales eran parte de la "especificación".
Neil
2

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:

({
  # (n+1)/2 to the other stack, n mod 2 to this stack
  <{({}[()]<(([{}]())<>{})<>>)}{}>
  # if 1 (n was odd) jump to the other stack and count the one
  {{}(<>)}{}
#end and push the sum -1, with a one under it
}<>[(())])
#use the one to get a power of two
{([()]{}<(({}){})>)}{}
#compare the power of two with the remainder after all the divisions
([({}[{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
MegaTom
fuente
1

Arce, 100 bytes (incluidos espacios)

IsProth:=proc(X)local n:=0;local x:=X-1;while x mod 2<>1 do x:=x/2;n:=n+1;end do;is(2^n>x);end proc:

Muy bien espaciados para la lectura:

IsProth := proc( X )
    local n := 0;
    local x := X - 1;
    while x mod 2 <> 1 do
        x := x / 2;
        n := n + 1;
    end do;
    is( 2^n > x );
end proc:

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.

DSkoog
fuente
1

Java 1.7, 49 43 bytes

Otros 6 bytes el polvo gracias a @charlie.

boolean g(int p){return p--<(p&-p)*(p&-p);}

¡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:

boolean f(int p){return(p-1&(1-p))>Math.sqrt(p);}

Aplicando el poder de dos al lado izquierdo de la expresión:

boolean g(int p){return Math.pow(p-1&(1-p),2)>p;}

Puede eliminar un solo byte si se permite que un valor numérico positivo represente 'verdadero' y un valor negativo 'falso':

double g(int p){return Math.pow(p-1&(1-p),2)-p;}

Desafortunadamente, debido a la "Conversión primitiva estrecha", uno no puede simplemente escribir esto en Java y obtener resultados correctos:

((p - 1 & (1 - p))^2) > p;

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 :(

MH
fuente
1
f = 47:boolean f(int p){return Math.sqrt(p--)<(p&-p);}
charlie
1
g = 43:boolean g(int p){return p--<(p&-p)*(p&-p);}
charlie
¡Buena esa! Sabía que tenía que haber una manera de deshacerse de las Math.*llamadas; simplemente no podía entender cómo! ¡Gracias!
MH.
1

Japt , 12 10 9 bytes

É&1-U)>Uq

Pruébalo en línea!

Port of Dennis 'Jelly responde de nuevo. - 1 gracias a @Shaggy.

randomdude999
fuente
-1puede ser É.
Shaggy
0

Cjam, 11 bytes

Como muchos de nosotros, aprovechamos la excelente solución de Dennis:

qi_(_W*&2#<

Pruébalo en línea

Un simmons
fuente
0

C (137 bytes)

int P(int N){int x=1,n=0,k=1,e=1,P=0;for(;e;n++){for(x=1,k=1;x&&x<N;k+=2){x=2<<n;x=x>k?x*k+1:0;if(x>N&&k==1)e=0;}if(x==N)P=1;}return P;}

Solo vine a leer las respuestas después de que lo intenté.

Considerando N=k*2^n+1con el condicional de k<2^n( k=1,3,5..yn=1,2,3..

Con n=1tenemos uno kdisponible para probar. A medida que aumentamos n, 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 nlak=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 ny 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.

IanC
fuente
0

Javascript ES7, 16 bytes

x=>x--<(-x&x)**2

El puerto de mi respuesta de Julia, que es un puerto de la respuesta de @ Dennis's Jelly.

¡Gracias @Charlie por 2 bytes guardados!

Mama Fun Roll
fuente
n=x=>x-1&1-x>x**.5; n(3)me da 0(en realidad me da 0 independientemente de la entrada)
titulado
Que navegador Puede ser solo eso.
Mama Fun Roll
Chrome 52. Firefox 48 da la misma respuesta paran=x=>x-1&1-x>Math.pow(x,0.5); n(3)
emitido el
Ok, es la precedencia del operador. Tiene que ser, (x-1&1-x)ya que sin ella, la prioridad del operador es en realidad:(x-1)&((1-x)>x**.5)
titulada
1
-1 byte: x=>x--**.5<(x&-x)ox=>x**.5<(--x&-x)
charlie
0

tinta , 60 bytes

=p(n)
~n-=n>1
~temp x=1
-(k){n%2:{n<x}->->}
~x+=x
~n=n/2
->k

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

= is_proth(number) =

/* It's easy to check if a number is one less than a Proth number.
   We take the number and divide it by 2 until we can't.
   Once we can't, we've found the smallest possible "k".
   If we also keep track of how many times we divided, we have our corresponding "2^n"
   All we have to do then is compare those
*/

~ number -= (number > 1)            // So, we first subtract one. Except this implementation won't ever halt for 0, so we don't subtract if the input is 1 (this is fine since the desired outputs for inputs 1 and 2 are the same)
~ temp power_of_two = 1             // We declare a variable to store our "2^n"
- (check)
  {
  - number % 2:                     // Once we can't divide by 2 anymore, we've found the smallest possible "k"
    {number < power_of_two}         // At that point, we print whether it's smaller than the "2^n" we found
    ->->                            // And then we return to where we were called from
  }

  ~ number = number / 2             // We keep dividing by 2 until we can't.
  ~ power_of_two += power_of_two    // and update our "2^n" as we go
-> check
Sara J
fuente
0

Código de máquina x86, 15 bytes

4F 89 F8 F7 D8 21 F8 0F AF C0 39 C7 19 C0 C3

Estos bytes definen una función que toma el argumento de entrada (un entero sin signo) en el EDIregistro, siguiendo la convención de llamada estándar del Sistema V para sistemas x86, y devuelve el resultado en el EAXregistro, como todas las convenciones de llamada x86.

En mnemotecnia de ensamblador:

4F          dec   edi            ; input -= 1
89 F8       mov   eax, edi       ; \ temp
F7 D8       neg   eax            ; |      =
21 F8       and   eax, edi       ; /        (input & -input)
0F AF C0    imul  eax, eax       ; temp *= temp
39 C7       cmp   edi, eax       ; set CF if (input < temp)
19 C0       sbb   eax, eax       ; EAX = -CF
C3          ret                  ; return with result in EAX
                                 ;  (-1 for Proth number; 0 otherwise)

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:

unsigned IsProthNumber(unsigned input)
{
    --input;
    unsigned temp  = (input & -input);
    temp          *= temp;
    return (input < temp) ? -1 : 0;
}

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 SBBinstrucción de 2 bytes en lugar de la SETBinstrucción de 3 bytes .

Cody Gray
fuente