Ganzzahlen teilen, kippen und neu kombinieren

16

Hintergrund

In der Mathematik ist bekannt, dass Ganzzahlen in eine Eins-zu-Eins-Entsprechung mit Paaren von Ganzzahlen gesetzt werden können. Es gibt viele Möglichkeiten, dies zu tun, und in dieser Herausforderung implementieren Sie eine davon und ihre inverse Operation.

Die Aufgabe

Ihre Eingabe ist eine positive Ganzzahl n > 0. Es ist bekannt, dass es eindeutige nicht negative ganze Zahlen gibt, a, b ≥ 0so dass . Ihre Ausgabe ist die "gespiegelte Version" der positiven Ganzzahl .n == 2a * (2*b + 1)n2b * (2*a + 1)

Sie können davon ausgehen, dass die Eingabe und Ausgabe in den Standard-Integer-Datentyp ohne Vorzeichen Ihrer Sprache passen.

Regeln und Wertung

Sie können entweder ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

Diese sind im Format angegeben in <-> out, da die zu implementierende Funktion eine eigene Umkehrung ist: Wenn Sie die Ausgabe darauf zurückführen, sollten Sie die ursprüngliche Eingabe erhalten.

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

Bestenliste

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren. Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

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

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

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

Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:

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

Code-Snippet anzeigen

code-golf number number-theory Zgarb
quelle
1
Witzig, dieses Problem wurde letzte Woche auf Anarchy Golf gepostet
feersum
@feersum Oh, ich wusste es nicht. Was für ein Zufall.
Zgarb
2
Obligatorisch xkcd.com/153
corsiKa

Antworten:

11

Jelly , 17 16 15 Bytes

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

Probieren Sie es online!

Wie es funktioniert

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
quelle
Warten Sie, implementieren Sie Operatoren in Jelly, um das Problem zu lösen? In diesem Fall LOL
Alexander Torstling
Ich bin nicht. Die einzige Zusage an Jelly, nachdem diese Aufforderung veröffentlicht wurde, war eine Aktualisierung der Dokumentation, und alle in dieser Antwort verwendeten Bediener wurden seit mindestens einem Monat implementiert. Fühlen Sie sich frei, um zu überprüfen
Dennis
Keine Sorge, ich kenne die Regeln oder so nicht, ich fand es einfach cool, dass Golfer ihre eigenen Sprachen erfinden!
Alexander Torstling
2
Und es gibt viele von ihnen. Check out Welche Programmiersprachen wurden von PPCG-Benutzern erstellt? .
Dennis
10

Pyth, 16 15 Bytes

*hyJ/PQ2^2.>QhJ

1 Byte danke an Dennis

Testsuite

Erläuterung:

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

MATL , 22 Bytes

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

Probieren Sie es online!

Erläuterung

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.
quelle
Sehr schön! Sie können Qfür 1+(dies wurde kürzlich eingeführt) und qfür verwenden 1-. Das spart auch Platz (mit dem man Hsowieso sparen könnte ). Siehe hier
Luis Mendo
@ LuisMendo Danke. Wusste das nicht.
Rainer P.
5
Gut gemacht, Luis mit MATL besiegt zu haben!
Stewie Griffin
6

Python 2, 39 Bytes

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

n & -ngibt die größte Potenz von 2, die sich teilt n. Es funktioniert, weil in Zweierkomplementarithmetik -n == ~n + 1. Wenn nhat k Nullen, wird ihr Komplement nehmen verursachen , es zu haben k Hinter diejenigen. Wenn Sie dann 1 hinzufügen, werden alle nachgestellten Einsen in Nullen geändert, und das 2 ^ k- Bit wird von 0 auf 1 geändert. Es -nendet also mit einer 1, gefolgt von k 0 (genau wie n), während nan allen höheren Stellen das entgegengesetzte Bit von vorhanden ist .

Feersum
quelle
Kannst du kurz erklären, wie es n&-nfunktioniert? Ich sehe, was dieser Trick tun, aber nicht wie :(
Erwan
n&-ngibt die höchste Potenz von 2 zurück, die sich teilt n.
Neil
@ Erwan erklärte ich über n & -n.
Feersum
Ich hatte das entsprechende Programm für Anarchy Golf bekommen n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, aber es sind zwei Zeichen hinter der besten Lösung.
Xnor
@xnor Hinweis: Die 59-Byte-Lösung (zumindest meine) funktioniert nicht für alle Werte von n.
Feersum
6

MATL , 25 26 Bytes

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

Dies verwendet die aktuelle Version (10.2.1) der Sprache / des Compilers.

Probieren Sie es online!

Erläuterung

Ziemlich unkompliziert, basierend auf roher Gewalt. Versucht alle Kombinationen von a und b , wählt die entsprechende aus und führt die erforderliche Berechnung durch.

: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
quelle
1
Hah! :-P In deiner eigenen Sprache geschlagen ... zum ersten Mal?
Stewie Griffin
@StewieGriffin Ja! Ein schöner Meilenstein :-)
Luis Mendo
5

Julia, 41 Bytes

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

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Wir definieren aals 1 + den Exponenten von 2 in der Primfaktorisierung von n. Da factorkehrt ein Dict, können wir verwenden , getmit einem Standardwert von 0 , falls die Primfaktorzerlegung enthält keine 2. Wir Verschiebung nach rechts Bit ndurch a, und auf diese Leistung 2 nehmen. Wir multiplizieren das mit 2a-1, um das Ergebnis zu erhalten.

Alex A.
quelle
4

Perl 5, 40 Bytes

38 Bytes plus 2 für -p

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

-pliest die STDIN in die Variable ein $_.

$i++,$_/=2until$_%2Inkremente $i(die bei 0 beginnen) und halbieren, $_bis $_mod 2 ungleich Null ist. Danach $_ist der ungerade Faktor der ursprünglichen Zahl und $ider Exponent von 2.

$_=2*$i+1<<$_/2-.5- Die rechte Seite von =ist nur die Formel für die gesuchte Zahl: {1 mehr als der doppelte Exponent von 2} mal {2 hoch dem halben ungeraden Faktor minus der Hälfte}}. "Times {2 to the power of…}" wird jedoch als "bitweise nach links verschoben von…" gewertet. Und diese rechte Seite ist zugeordnet $_.

Und -pdruckt $_.

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

JavaScript ES6, 36 33 Bytes

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

Meines Wissens wird das Math.clz32kürzer sein als herumzuspielen toString(2).length.

Bearbeiten: 3 Bytes dank @ user81655 gespeichert.

Neil
quelle
Nett. Sie können auch ein paar Bytes sparen, indem Sie n&-neine Variable n=>63-2*Math.clz32(x=n&-n)<<n/x/2
festlegen
@ user81655 Danke; Ich wünschte nur, ich hätte es gebrauchen können n&=-n, aber ich brauche es nwieder ...
Neil
1

PARI / GP , 38 Bytes

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

Beachten Sie, dass >>und \haben die gleiche Priorität und sind berechnet von links nach rechts, so dass der letzte Teil sein kann , n>>k\2als vielmehr (n>>k)\2. Die ungolfed Version würde klexikalisch machen mit my:

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