Dividir, voltear y recombinar enteros

16

Antecedentes

Es bien sabido en matemáticas que los enteros se pueden poner en una correspondencia uno a uno con pares de enteros. Hay muchas formas posibles de hacer esto, y en este desafío, implementará una de ellas y su operación inversa.

La tarea

Su entrada es un número entero positivo n > 0. Se sabe que existen enteros únicos no negativos, a, b ≥ 0tales como . Su salida es la "versión invertida" de , el entero positivo .n == 2a * (2*b + 1)n2b * (2*a + 1)

Puede suponer que la entrada y la salida se ajustan al tipo de datos entero sin signo estándar de su idioma.

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

Estos se dan en el formato in <-> out, ya que la función que se implementará es su propio inverso: si le devuelve la salida, debe obtener la entrada original.

1 <-> 1
2 <-> 3
4 <-> 5
6 <-> 6
7 <-> 8
9 <-> 16
10 <-> 12
11 <-> 32
13 <-> 64
14 <-> 24
15 <-> 128
17 <-> 256
18 <-> 48
19 <-> 512
20 <-> 20
28 <-> 40
30 <-> 384
56 <-> 56
88 <-> 224
89 <-> 17592186044416

Tabla 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, usando la siguiente plantilla de Markdown:

## Language Name, N bytes

¿Dónde Nestá 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 (p. Ej., Porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de los intérpretes 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

Mostrar fragmento de código

code-golf number number-theory Zgarb
fuente
1
Es curioso, este problema fue publicado en anarchy golf la semana pasada
feersum
@feersum Oh, no estaba al tanto. Qué casualidad.
Zgarb
2
Obligatorio xkcd.com/153
corsiKa

Respuestas:

11

Jalea , 17 16 15 bytes

BUi1µ2*³:2*×Ḥ’$

Pruébalo en línea!

Cómo funciona

BUi1µ2*³:2*×Ḥ’$    Main link. Input: n

B                  Convert n to base 2.
 U                 Reverse the array of binary digits.
  i1               Get the first index (1-based) of 1.
                   This yields a + 1.
    µ              Begin a new, monadic chain. Argument: a + 1
     2*            Compute 2 ** (a+1).
       ³:          Divide n (input) by 2 ** (a+1).
                   : performs integer division, so this yields b.
         2*        Compute 2 ** b.
              $    Combine the two preceding atoms.
            Ḥ      Double; yield 2a + 2.
             ’     Decrement to yield 2a + 1.
           ×       Fork; multiply the results to the left and to the right.
Dennis
fuente
Espera, ¿estás implementando operadores en Jelly para adaptarse al problema? En ese caso LOL
Alexander Torstling
No soy. El único compromiso con Jelly después de que se publicó este desafío fue una actualización de la documentación, y todo el operador utilizado en esta respuesta se implementó durante al menos un mes. Siéntase libre de verificar
Dennis
No se preocupe, no estoy familiarizado con las reglas ni nada, ¡solo pensé que era genial que el golf haya llegado a las personas que inventan sus propios idiomas!
Alexander Torstling
2
Y hay muchos de ellos. Consulte ¿Qué lenguajes de programación han creado los usuarios de PPCG? .
Dennis
10

Pyth, 16 15 bytes

*hyJ/PQ2^2.>QhJ

1 byte gracias a Dennis

Banco de pruebas

Explicación:

*hyJ/PQ2^2.>QhJ
                    Implicit: Q = eval(input())
     PQ             Take the prime factorization of Q.
    /  2            Count how many 2s appear. This is a.
   J                Save it to J.
  y                 Double.
 h                  +1.
          .>QhJ     Shift Q right by J + 1, giving b.
        ^2          Compute 2 ** b.
*                   Multiply the above together, and print implicitly.
isaacg
fuente
7

MATL , 22 bytes

Yft2=XK~)pq2/2w^Ks2*Q*

Pruébalo en línea!

Explicación

Yf      % factor
t       % duplicate
2=      % compare to 2 (yields a logical array)
XK      % save a copy of that to variable K
~)      % keep only values != 2 in the factors array
p       % multiply that factors
q2/     % product - 1 / 2
2w^     % 2^x

K       % load variable K (the logical array)
s       % sum (yields the number of 2s)
2*Q     % count * 2 + 1

*       % multiply both values
Rainer P.
fuente
¡Muy agradable! Puede usar Qpara 1+(esto se ha introducido recientemente) y qpara 1-. Eso también ahorra un espacio (que podría ahorrar de Htodos modos). Ver aquí
Luis Mendo
@LuisMendo Gracias. No conocía esa característica.
Rainer P.
55
¡Bien hecho superando a Luis usando MATL!
Stewie Griffin
6

Python 2, 39 bytes

lambda n:2*len(bin(n&-n))-5<<n/2/(n&-n)

n & -nda la mayor potencia de 2 que divide n. Funciona porque en la aritmética de complemento a dos, -n == ~n + 1. Si ntiene k ceros al final, tomar su complemento hará que tenga k al final. Luego, agregar 1 cambiará todos los finales a ceros, y cambiará el bit 2 ^ k de 0 a 1. Entonces -ntermina con un 1 seguido de k 0 (igual que n), mientras que tiene el bit opuesto nen todos los lugares más altos.

Feersum
fuente
¿Puedes explicar brevemente cómo n&-nfunciona? veo lo que hace este truco pero no cómo :(
Erwan
n&-ndevuelve la potencia más alta de 2 que divide n.
Neil
@Erwan lo expliqué n & -n.
feersum
Obtuve el programa correspondiente en Anarchy golf n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, pero hay dos caracteres detrás de la mejor solución.
xnor
@xnor Sugerencia: la solución de 59 bytes (bueno, al menos la mía) no funciona para todos los valores de n.
feersum
6

MATL , 25 26 bytes

:qt2w^w!2*Q*G=2#f2*q2bq^*

Esto usa la versión actual (10.2.1) del lenguaje / compilador.

Pruébalo en línea!

Explicación

Bastante sencillo, basado en la fuerza bruta. Intenta todas las combinaciones de a y b , selecciona la adecuada y realiza el cálculo requerido.

:q          % implicit input "n". Generate row vector [0,1,...,n-1], say "x"
t2w^        % duplicate and compute 2^x element-wise
w!2*Q       % swap, transpose to column vector, compute 2*x+1
*           % compute all combinations of products. Gives 2D array
G=2#f       % find indices where that array equals n
2*q2bq^*    % apply operation to flipped values
Luis Mendo
fuente
1
Ja! :-P Golpeado en tu propio idioma ... ¿primera vez?
Stewie Griffin
@StewieGriffin ¡Sí! Un buen hito :-)
Luis Mendo
5

Julia, 41 bytes

n->2^(n>>(a=get(factor(n),2,0)+1))*(2a-1)

Esta es una función anónima que acepta un entero y devuelve un entero. Para llamarlo, asígnelo a una variable.

Definimos acomo 1 + el exponente de 2 en la factorización prima de n. Dado que factordevuelve una Dict, se pueden usar getcon un valor por defecto de 0 en caso de que la descomposición en factores primos no contiene 2. desplazamiento de bits a la derecha npor a, y tomar de 2 a este poder. Multiplicamos eso por 2a-1para obtener el resultado.

Alex A.
fuente
4

Perl 5, 40 bytes

38 bytes más 2 para -p

$i++,$_/=2until$_%2;$_=2*$i+1<<$_/2-.5

-plee el STDIN en la variable $_.

$i++,$_/=2until$_%2incrementos $i(que comienzan en 0) y se reducen a la mitad $_hasta $_que no sea cero mod 2. Después de eso, $_es el factor impar del número original y $ies el exponente de 2.

$_=2*$i+1<<$_/2-.5- El lado derecho de la =es solo la fórmula para el número buscado: {1 más del doble del exponente de 2} veces {2 a la potencia de {la mitad del factor impar menos la mitad}}. Pero "times {2 to the power of ...}" se juega como "un poco desplazado hacia la izquierda por ...". Y ese lado derecho está asignado a $_.

Y -pgrabados $_.

msh210
fuente
2

C, 49 bytes

a;f(n){for(a=0;n%2-1;a++)n/=2;return 2*a+1<<n/2;}
Level River St
fuente
2

JavaScript ES6, 36 33 bytes

n=>63-2*Math.clz32(b=n&-n)<<n/b/2

Tengo entendido que Math.clz32va a ser más corto que jugar contoString(2).length .

Editar: Guardado 3 bytes gracias a @ user81655.

Neil
fuente
Agradable. También puede guardar algunos bytes configurando n&-nuna variable:n=>63-2*Math.clz32(x=n&-n)<<n/x/2
user81655
@ user81655 Gracias; Solo desearía haberlo usado n&=-n, pero necesito notra vez ...
Neil
1

PARI / GP , 38 bytes

f(n)=k=valuation(n,2);(2*k+1)<<(n>>k\2)

Tenga en cuenta que >>y \tienen la misma precedencia y se calculan de izquierda a derecha, por lo que la última parte puede ser en n>>k\2lugar de (n>>k)\2. La versión no golfista sería kléxica con my:

f(n)=
{
  my(k=valuation(n,2));
  (2*k+1) << ((n>>k)\2);
}
Charles
fuente