Fractionner, retourner et recombiner des entiers

16

Contexte

Il est bien connu en mathématiques que les entiers peuvent être mis en correspondance biunivoque avec des paires d'entiers. Il existe de nombreuses façons de le faire, et dans ce défi, vous allez mettre en œuvre l'un d'entre eux et son fonctionnement inverse.

La tâche

Votre entrée est un entier positif n > 0. On sait qu'il existe des entiers non négatifs uniques a, b ≥ 0tels que . Votre sortie est la "version inversée" de , l'entier positifn == 2a * (2*b + 1)n2b * (2*a + 1) .

Vous pouvez supposer que l'entrée et la sortie correspondent au type de données entier non signé standard de votre langue.

Règles et notation

Vous pouvez écrire soit un programme complet soit une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test

Celles-ci sont données au format in <-> out, car la fonction à implémenter est son propre inverse: si vous lui renvoyez la sortie, vous devriez obtenir l'entrée d'origine.

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

Classement

Voici un extrait de pile pour générer à la fois un classement régulier et un aperçu des gagnants par langue. Pour vous assurer que votre réponse apparaît, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

## Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les rayant. Par exemple:

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

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou si vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

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

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de classement:

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

Afficher l'extrait de code

code-golf number number-theory Zgarb
la source
1
Drôle, ce problème a été signalé sur anarchy golf la semaine dernière
feersum
@feersum Oh, je n'étais pas au courant. Quelle coïncidence.
Zgarb
2
Obligatoire xkcd.com/153
corsiKa

Réponses:

11

Gelée , 17 16 15 octets

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

Essayez-le en ligne!

Comment ça fonctionne

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
la source
Attendez, implémentez-vous des opérateurs dans Jelly pour répondre au problème? Dans ce cas LOL
Alexander Torstling
Je ne suis pas. Le seul engagement envers Jelly après la publication de ce défi était une mise à jour de la documentation, et tous les opérateurs utilisés dans cette réponse ont été mis en œuvre depuis au moins un mois. N'hésitez pas à vérifier
Dennis
Pas de soucis, je ne connais pas les règles ou quoi que ce soit, je pensais juste que c'était cool que le golf soit venu aux gens inventant leurs propres langues!
Alexander Torstling
2
Et il y en a beaucoup. Découvrez quels langages de programmation ont été créés par les utilisateurs de PPCG? .
Dennis
10

Pyth, 16 15 octets

*hyJ/PQ2^2.>QhJ

1 octet merci à Dennis

Suite de tests

Explication:

*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
la source
7

MATL , 22 octets

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

Essayez-le en ligne!

Explication

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.
la source
Très agréable! Vous pouvez utiliser Qpour 1+(cela a été introduit récemment) et qpour 1-. Cela permet également d'économiser un espace (avec lequel vous pourriez économiser de Htoute façon). Voir ici
Luis Mendo
@LuisMendo Merci. Je ne connaissais pas cette fonctionnalité.
Rainer P.
5
Bravo à Luis en utilisant MATL!
Stewie Griffin
6

Python 2, 39 octets

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

n & -ndonne la plus grande puissance de 2 qui se divise n. Cela fonctionne parce que dans l' arithmétique en complément à deux, -n == ~n + 1. Si na k zéros de fin, la prise de son complément lui fera avoir k zéros de fin. Ensuite, l'ajout de 1 changera tous les zéros de fin et changera le bit 2 ^ k de 0 à 1. Donc, -nse termine par un 1 suivi de k 0 (tout comme n), tout en ayant le bit opposé de ntous les endroits supérieurs.

feersum
la source
pouvez-vous expliquer brièvement comment ça n&-nmarche? je vois ce que cette astuce fait mais pas comment :(
Erwan
n&-nrenvoie la puissance la plus élevée de 2 qui divise n.
Neil
@Erwan, j'ai expliqué n & -n.
feersum
J'avais obtenu le programme correspondant sur le golf Anarchy n=1;exec"c=n&-n;print n,':',2*len(bin(c))-5<<n/2/c;n+=1;"*100, mais c'est deux caractères derrière la meilleure solution.
xnor
@xnor Astuce: la solution de 59 octets (enfin, la mienne au moins) ne fonctionne pas pour toutes les valeurs de n.
feersum
6

MATL , 25 26 octets

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

Cela utilise la version actuelle (10.2.1) du langage / compilateur.

Essayez-le en ligne!

Explication

Assez simple, basé sur la force brute. Essaie toutes les combinaisons de a et b , sélectionne la bonne et effectue le calcul requis.

: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
la source
1
Hah! :-P Battu dans votre propre langue ... première fois?
Stewie Griffin
@StewieGriffin Yep! Une belle étape :-)
Luis Mendo
5

Julia, 41 octets

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

Il s'agit d'une fonction anonyme qui accepte un entier et renvoie un entier. Pour l'appeler, affectez-le à une variable.

Nous définissons acomme 1 + l'exposant de 2 dans la décomposition en facteurs premiers de n. Depuis le factorrendement d' un Dict, nous pouvons utiliser getavec une valeur par défaut de 0 dans le cas où le premier factorisation ne contient pas 2. Nous décalage de bits à droite npar a, et prendre 2 à ce pouvoir. Nous multiplions cela par 2a-1pour obtenir le résultat.

Alex A.
la source
4

Perl 5, 40 octets

38 octets plus 2 pour -p

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

-plit le STDIN dans la variable $_.

$i++,$_/=2until$_%2incrémente $i(qui commence à 0) et divise par deux $_jusqu'à ce qu'il $_soit différent de zéro mod 2. Après cela, $_est le facteur impair du nombre d'origine, et $iest l'exposant de 2.

$_=2*$i+1<<$_/2-.5- Le côté droit de la =est juste la formule du nombre recherché: {1 plus de deux fois l'exposant de 2} fois {2 à la puissance de {la moitié du facteur impair moins la moitié}}}. Mais «fois {2 à la puissance de…}» est considéré comme «décalé vers la gauche par…». Et ce côté droit est affecté à $_.

Et -pimprime $_.

msh210
la source
2

C, 49 octets

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

JavaScript ES6, 36 33 octets

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

Je crois comprendre que cela Math.clz32va être plus court que de jouer avec toString(2).length.

Edit: sauvé 3 octets grâce à @ user81655.

Neil
la source
Agréable. Vous pouvez également enregistrer quelques octets en définissant n&-nune variable:n=>63-2*Math.clz32(x=n&-n)<<n/x/2
user81655
@ user81655 Merci; Je souhaite seulement que j'aurais pu utiliser n&=-n, mais j'en ai nencore besoin ...
Neil
1

PARI / GP , 38 octets

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

Notez que >>et \ont la même priorité et sont calculés de gauche à droite, de sorte que la dernière partie peut être n>>k\2plutôt que (n>>k)\2. La version non golfée serait klexicale avec my:

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