¿Cómo es este número Fermat?

13

Los números de Fermat son enteros positivos que se pueden expresar como 2 2 x +1 con un entero x.

Ahora definamos un atributo de un número llamado "Fermat-ness":

  • La Fermatness del número es uno menos que la longitud de la cadena de poderes de dos, comenzando desde la base, con poderes de dos expandidos para maximizar la Fermatness.
  • Un número que no es un número de Fermat tiene la Fermat-ness de cero.

Entonces, 17 (= 2 2 2 2 0 +1) tiene Fermat-ness tres.

Desafío

Dado un entero positivo distinto de cero como entrada, genera la Fermatness del número.

Reglas

  • Puede tomar la entrada en binario, decimal, hexadecimal, como bignum, o cualquier formato que le permita jugar mejor al golf.
  • Su solución debe poder procesar números con longitudes de bits superiores a 64, independientemente de la representación que utilice.
  • Potencias enteras no negativas solamente.
  • Las lagunas estándar están, por supuesto, prohibidas.
  • Este es el , por lo que gana la respuesta más corta.

Casos de prueba

Estos están en formato input->output. La entrada está en hexadecimal para ahorrar espacio.

10000000000000000000000000000000000000000000000000000000000000001 -> 2
1000000000000BC00000000000000000000000000000000001000000000000001 ->0
1234567890ABCDEF -> 0
100000000000000000000000000000001 -> 1
5 -> 2
11 -> 3
10001 -> 4
101 -> 1

Lo mismo en decimal:

115792089237316195423570985008687907853269984665640564039457584007913129639937 -> 2
115792089237316497527923305698859709742143344804209838213621568094470773145601 -> 0
1311768467294899695 -> 0
340282366920938463463374607431768211457 -> 1
5 ->2
17 -> 3
65537 -> 4
257 -> 1

Gracias a geokavel por su valiosa aportación en el sandbox.

HAEM
fuente
1
Si ingreso 1111, ¿cómo sabes que está en binario, decimal o hexadecimal?
J42161217
1
@ Jenny_mathy Quería que el respondedor decidiera qué formato de entrada quieren.
HAEM
@ Mr.Xcoder En el sandbox surgió que realmente no hay muchos números de Fermat de 64 bits o menos. Estoy afirmando que la pregunta es intrínsecamente sobre bignums, por lo que puedo exigir el procesamiento de bignum.
HAEM
2
@ HeikkiMäenpää Recuerda, no importa lo que otros puedan recomendar, el desafío es tuyo y puedes hacer lo que quieras.
isaacg
3
Creo que es demasiado pronto para aceptar. Por lo general, espere 1 o 2 semanas. ¡Algunos dicen que nunca aceptes!
geokavel

Respuestas:

7

Jalea , 15 14 bytes

1 byte gracias a Jonathan Allan.

’µBḊ⁸LṀ?µÐĿḊḊL

Pruébalo en línea!

Monja permeable
fuente
2
Guardar un byte con: BḊCL⁸Ạ?->BḊ⁸LṀ?
Jonathan Allan
1

Python 2 , 103 81 bytes

n=input()-1
i=l=0
while 2**2**i<=n:
 if n==2**2**i:n=2**i;i=-1;l+=1
 i+=1
print l

Pruébalo en línea!

Me di cuenta de que no ser estúpido ayudaría a reducir mi número de bytes, así que lo hice. También exponenciación frente a logaritmos.

Arnold Palmer
fuente
0

RProgN 2 , 75 bytes

«\`n=1\]{1-\n*\]}:[»`^=«1-`n=001{]2\^2\^ne{2\^`n=1+0}{1+}?]2\^2\^n>¬}:[»`¤=

Pruébalo en línea!

Son solo 70 bytes si no agrega el «»'¤= que asigna el cálculo de Fermatness al ¤personaje. Si lo hace, deberá colocar el número en la sección Encabezado de TIO en lugar de en el Pie de página como está ahora.

Esto utiliza efectivamente la misma lógica que mi respuesta de Python, por lo que si no te importa cómo funciona RProgN 2, solo mira esa para obtener una explicación de lo que está sucediendo. De otra manera

Desglose del código:

«\`n=1\]{1-\n*\]}:[»`^=
«                  »`^=`                            # Create a local function and assign it to the ^ character (x y ^ is x to the power of y)
 \`n=                                               # Swap the top two values of the stack and assign the new top to the variable n
     1\]                                            # Push a 1 (our starting point for x to the y), swap with the y value, then duplicate y
        {       }:                                  # Start a while loop that pops the top stack value and loops if it is truthy
         1-                                         # Subtract 1 from y to keep a tally of how many multiplications we've done
           \n*                                      # Swap the counter with our current value and multiply it by n
              \]                                    # Swap this new value with the current value of y, and duplicate it to be used as the truthy value for the loop

«1-`n=001{]2\^2\^ne{2\^`n=1+0}{1+}?]2\^2\^n>¬}:[»`¤=# The main Fermatness function (x ¤ to get the Fermatness of x)
«                                               »`¤=# Create another local function for this calculation
 1-`n=                                              # Decrement the input by 1 and assign it to n
      001                                           # Push a counter for Fermatness, a counter for calculating 2^2^i, and an initial truthy value
         {                                   }:     # Start a while loop for calculating the Fermatness
          ]2\^2\^ne                                 # Duplicate i, calculate 2^2^i, and compare it to n
                   {         }{  }?                 # Start an if statement based on the equality of 2^2^i and n
                    2\^`n=                          # n==2^2^i, so set n to 2^i (same as saying n=log_2(n))
                          1+0                       # Increment the Fermatness counter and reset i
                               1+                   # n!=2^2^i, so just increment i
                                   ]2\^2\^n>¬       # Duplicate the counter and check if 2^2^i<=n, if true the loop continues, else it exits
                                               [    # Pop i from the stack, leaving us with just the Fermatness counter

Desafortunadamente, la función de registro Šy la función de exponenciación normal ^carecen de la precisión para hacer esto de forma nativa, por lo que tuve que redefinir cómo funcionaba la exponenciación ya que la multiplicación conlleva mucha más precisión. Sin esa redefinición, esta respuesta sería 23 bytes más corta.

Arnold Palmer
fuente