Podziel, odwróć i ponownie połącz liczby całkowite

16

tło

W matematyce dobrze wiadomo, że liczby całkowite można umieszczać w korespondencji jeden-do-jednego z parami liczb całkowitych. Można to zrobić na wiele sposobów, aw tym wyzwaniu zaimplementujesz jeden z nich i jego odwrotne działanie.

Zadanie

Twój wkład jest dodatnią liczbą całkowitą n > 0. Wiadomo, że istnieją unikalne nieujemne liczby całkowite, a, b ≥ 0takie jak . Twój wynik to „odwrócona wersja” dodatniej liczby całkowitej .n == 2a * (2*b + 1)n2b * (2*a + 1)

Możesz założyć, że dane wejściowe i wyjściowe pasują do standardowego typu danych całkowitych bez znaku w Twoim języku.

Zasady i punktacja

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Są one podane w formacie in <-> out, ponieważ funkcja, która ma zostać zaimplementowana, jest odwrotna: jeśli podasz z powrotem dane wyjściowe, powinieneś otrzymać oryginalne dane wejściowe.

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

Tabela liderów

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka. Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz dołączyć wiele numerów do nagłówka (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że faktyczny wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie tabeli wyników:

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

Pokaż fragment kodu

code-golf number number-theory Zgarb
źródło
1
Zabawne, ten problem został opublikowany w anarchii golfowej w zeszłym tygodniu
feersum
@feersum Och, nie byłem świadomy. Co za zbieg okoliczności.
Zgarb
2
Obowiązkowe xkcd.com/153
corsiKa

Odpowiedzi:

11

Galaretka , 17 16 15 bajtów

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

Wypróbuj online!

Jak to działa

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
źródło
Czekaj, czy wdrażasz operatorów w Galaretce, aby dopasować się do problemu? W takim przypadku LOL
Alexander Torstling
Nie jestem. Popełnić tylko do Jelly po to wyzwanie została wysłana była aktualizacja dokumentacji i wszystkie operator stosuje się w tej odpowiedzi zostały wdrożone przez co najmniej miesiąc. Zapraszam do weryfikacji
Dennis
Nie martw się, nie znam zasad ani nic takiego. Po prostu pomyślałem, że to fajne, że golf przyszedł do ludzi, którzy wymyślili swoje własne języki!
Alexander Torstling
2
I jest ich dużo. Sprawdź Jakie języki programowania zostały utworzone przez użytkowników PPCG? .
Dennis
10

Pyth, 16 15 bajtów

*hyJ/PQ2^2.>QhJ

1 bajt dzięki Dennisowi

Zestaw testowy

Wyjaśnienie:

*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
źródło
7

MATL , 22 bajty

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

Wypróbuj online!

Wyjaśnienie

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.
źródło
Bardzo dobrze! Możesz użyć Qdla 1+(zostało to niedawno wprowadzone) i qdla 1-. To także oszczędza miejsce (które i tak można zaoszczędzić H). Zobacz tutaj
Luis Mendo
@LuisMendo Thanks. Nie znam tej funkcji.
Rainer P.
5
Brawo, pokonując Luisa za pomocą MATL!
Stewie Griffin
6

Python 2, 39 bajtów

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

n & -ndaje największą siłę 2, która dzieli n. To działa, ponieważ w uzupełnionych do dwóch arytmetyka -n == ~n + 1. Jeśli nma k końcowych zer, pobranie jego dopełnienia spowoduje, że będzie mieć k zer zerowych . Następnie dodanie 1 zmieni wszystkie końcowe zera na zera i zmieni bit 2 ^ k z 0 na 1. Więc -nkończy się na 1, po którym następuje k 0 (podobnie jak n), mając jednocześnie przeciwny bit nwe wszystkich wyższych miejscach.

feersum
źródło
czy możesz krótko wyjaśnić, jak n&-ndziała? widzę, co robi ta sztuczka, ale nie jak :(
Erwan
n&-nzwraca najwyższą potęgę z 2, które dzielą n.
Neil
@Erwan wyjaśniłem n & -n.
feersum
Otrzymałem odpowiedni program na Anarchy Golf n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, ale są dwa znaki za najlepszym rozwiązaniem.
xnor
@ xnor Podpowiedź: 59-bajtowe rozwiązanie (cóż, przynajmniej moje) nie działa dla wszystkich wartości n.
feersum
6

MATL , 25 26 bajtów

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

Używa bieżącej wersji (10.2.1) języka / kompilatora.

Wypróbuj online!

Wyjaśnienie

Całkiem proste, oparte na brutalnej sile. Próbuje wszystkich kombinacji a i b , wybiera odpowiednią i wykonuje wymagane obliczenia.

: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
źródło
1
Hah! :-P Pobity w swoim własnym języku ... pierwszy raz?
Stewie Griffin
@StewieGriffin Tak! Miły kamień milowy :-)
Luis Mendo
5

Julia, 41 bajtów

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

Jest to anonimowa funkcja, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.

Definiujemy ajako 1 + wykładnik 2 w pierwotnym rozkładzie na czynniki n. Od factorZwraca Dictmożemy korzystać getz domyślnej wartości 0 w przypadku głównym faktoryzacji nie zawiera 2. We właściwej bitowego przesunięcia nprzez ai Take 2 do tej mocy. Pomnożymy to, 2a-1aby uzyskać wynik.

Alex A.
źródło
4

Perl 5, 40 bajtów

38 bajtów plus 2 dla -p

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

-p wczytuje STDIN do zmiennej $_ .

$i++,$_/=2until$_%2inkrementuje $i(który zaczyna się od 0) i zmniejsza o połowę, $_aż $_będzie niezerowy mod 2. Następnie $_jest nieparzystym współczynnikiem oryginalnej liczby i $ijest wykładnikiem 2.

$_=2*$i+1<<$_/2-.5- Prawa strona =to tylko wzór na szukaną liczbę: {1 ponad dwukrotność wykładnika 2} razy {2 do potęgi {połowa nieparzystego czynnika minus pół}}. Ale „czasy {2 do potęgi…}” są golfowane jako „przesunięte nieco w lewo o…”. I ta prawa strona jest przypisana $_.

I -pdruki $_.

msh210
źródło
2

C, 49 bajtów

a;f(n){for(a=0;n%2-1;a++)n/=2;return 2*a+1<<n/2;}
Level River St
źródło
2

JavaScript ES6, 36 33 bajtów

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

Rozumiem, że Math.clz32będzie to krótsze niż bawienie siętoString(2).length .

Edycja: Zapisano 3 bajty dzięki @ user81655.

Neil
źródło
Ładny. Możesz także zapisać kilka bajtów, ustawiając n&-nzmienną:n=>63-2*Math.clz32(x=n&-n)<<n/x/2
user81655
@ user81655 Dzięki; Chciałbym tylko móc z niego skorzystać n&=-n, ale potrzebuję nponownie ...
Neil
1

PARI / GP , 38 bajtów

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

Należy pamiętać, że >>i \mają ten sam priorytet i są obliczane od lewej do prawej, tak ostatnia część może być n>>k\2zamiast (n>>k)\2. Wersja bez golfa uczyniłaby kleksykalną z my:

f(n)=
{
  my(k=valuation(n,2));
  (2*k+1) << ((n>>k)\2);
}
Charles
źródło