Dividir, inverter e recombinar números inteiros

16

fundo

É bem conhecido na matemática que números inteiros podem ser colocados em uma correspondência individual com pares de números inteiros. Existem muitas maneiras possíveis de fazer isso e, neste desafio, você implementará uma delas e sua operação inversa.

A tarefa

Sua entrada é um número inteiro positivo n > 0. Sabe-se que existem números inteiros não negativos únicos, a, b ≥ 0tais que . Sua saída é a "versão invertida" do número inteiro positivo .n == 2a * (2*b + 1)n2b * (2*a + 1)

Você pode assumir que a entrada e a saída se encaixam no tipo de dados inteiro não assinado padrão do seu idioma.

Regras e pontuação

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

Elas são fornecidas no formato in <-> out, já que a função a ser implementada é sua própria inversa: se você devolver a saída a ela, deverá obter a 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

Entre os melhores

Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma. Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

## Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Se você deseja incluir vários números no seu cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

## Perl, 43 + 2 (-p flag) = 45 bytes

Você também pode transformar o nome do idioma em um link que será exibido no snippet da tabela de classificação:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

Mostrar snippet de código

code-golf number number-theory Zgarb
fonte
1
Engraçado, esse problema foi publicado no anarchy golf na semana passada
feersum
@feersum Oh, eu não estava ciente. Que coincidência.
Zgarb 27/01
2
Obrigatória xkcd.com/153
corsiKa

Respostas:

11

Geléia , 17 16 15 bytes

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

Experimente online!

Como 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
fonte
Espere, você está implementando operadores no Jelly para se adequar ao problema? Nesse caso, LOL
Alexander Torstling 28/01
Eu não sou. O único commit no Jelly após o lançamento deste desafio foi uma atualização da documentação e todo o operador usado nesta resposta foi implementado por pelo menos um mês. Sinta-se livre para verificar
Dennis
Não se preocupe, eu não estou familiarizado com as regras nem nada, apenas pensei que era legal o golfe chegar às pessoas que inventavam seus próprios idiomas!
Alexander Torstling
2
E há muitos deles. Confira Quais linguagens de programação foram criadas pelos usuários do PPCG? .
Dennis
10

Pitão, 16 15 bytes

*hyJ/PQ2^2.>QhJ

1 byte graças a Dennis

Suíte de teste

Explicação:

*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
fonte
7

MATL , 22 bytes

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

Experimente online!

Explicação

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.
fonte
Muito agradável! Você pode usar Qpara 1+(isto foi introduzido recentemente) e qpara 1-. Isso também economiza um espaço (com o qual você pode economizar de Hqualquer maneira). Veja aqui
Luis Mendo
@LuisMendo Thanks. Não conhecia esse recurso.
Rainer P.
5
Muito bem derrotado Luis usando MATL!
Stewie Griffin
6

Python 2, 39 bytes

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

n & -ndá a maior potência de 2 que divide n. Funciona porque na aritmética do complemento de dois -n == ~n + 1,. Se ntem k zeros à direita, tendo o seu complemento fará com que ele tem k queridos fuga. A adição de 1 mudará todos os valores finais para zeros e alterará o bit 2 ^ k de 0 para 1. Portanto, -ntermina com 1 seguido de k 0 (exatamente como n), mantendo o bit oposto nem todos os lugares mais altos.

feersum
fonte
você pode explicar em breve como n&-nfunciona? i ver o que este truque fazer, mas não como :(
Erwan
n&-nretorna a potência mais alta de 2 que divide n.
Neil
@ Erwan eu expliquei sobre n & -n.
precisa saber é
Eu tinha conseguido o programa correspondente no golfe Anarchy n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, mas há dois caracteres por trás da melhor solução.
Xnor
@ Dica xnor: a solução de 59 bytes (bem, pelo menos a minha) não funciona para todos os valores de n.
precisa saber é
6

MATL , 25 26 bytes

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

Isso usa a versão atual (10.2.1) do idioma / compilador.

Experimente online!

Explicação

Bem simples, com base na força bruta. Tenta todas as combinações de a e b , seleciona a apropriada e faz o cálculo necessário.

: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
fonte
1
Hah! :-P Batido no seu próprio idioma ... primeira vez?
Stewie Griffin
@StewieGriffin Yep! Um marco legal :-)
Luis Mendo
5

Julia, 41 bytes

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

Esta é uma função anônima que aceita um número inteiro e retorna um número inteiro. Para chamá-lo, atribua-o a uma variável.

Definimos acomo 1 + o expoente de 2 na fatoração primária de n. Como factorretorna a Dict, podemos usar getcom o valor padrão 0, caso a fatoração principal não contenha 2. Mudamos corretamente o bitn de a, e ter 2 a este poder. Nós multiplicamos isso por 2a-1para obter o resultado.

Alex A.
fonte
4

Perl 5, 40 bytes

38 bytes mais 2 para -p

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

-p lê o STDIN na variável $_ .

$i++,$_/=2until$_%2incrementos $i(que começa em 0) e diminui pela metade $_até o $_mod 2 diferente de zero. Depois disso, $_é o fator ímpar do número original e $ié o expoente de 2.

$_=2*$i+1<<$_/2-.5 - O lado direito do = é apenas a fórmula para o número procurado: {1 mais que o dobro do expoente de 2} vezes {2 à potência de {metade do fator ímpar menos menos a metade}}. Mas "times {2 to the power of ...}" é jogado como "pouco deslocado para a esquerda por ...". E esse lado direito está atribuído $_.

E -pimprime $_.

msh210
fonte
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
fonte
2

JavaScript ES6, 36 33 bytes

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

Meu entendimento é que Math.clz32 será mais curto do que brincar toString(2).length.

Editar: salvou 3 bytes graças a @ user81655.

Neil
fonte
Agradável. Você também pode salvar alguns bytes configurando n&-npara uma variável:n=>63-2*Math.clz32(x=n&-n)<<n/x/2
user81655 28/08
@ user81655 Obrigado; Eu só desejo que eu poderia ter usado n&=-n, mas eu preciso nde novo ...
Neil
1

PARI / GP , 38 bytes

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

Observe que >>e \têm a mesma precedência e são computados da esquerda para a direita, para que a última parte possa ser n>>k\2melhor que (n>>k)\2. A versão não-gasta tornaria klexical com my:

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