Considérons la séquence numérique suivante:

$0, \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}, \frac{1}{16}, \frac{3}{16}, \frac{5}{16}, \frac{7}{16}, \frac{9}{16}, \frac{11}{16}, \frac{13}{16}, \frac{15}{16}, \frac{1}{32}, \frac{3}{32}, \frac{5}{32}, \dots$

Il énumère toutes les fractions binaires dans l'intervalle unitaire .$[0, 1)$

(Pour faciliter ce défi, le premier élément est optionnel: vous pouvez le sauter et considérer que la séquence commence par 1/2.)

Tâche

Ecrivez un programme (programme complet ou une fonction) qui ...

Choisissez l'un de ces comportements:

• Entrée n, sortie nième élément de la séquence (indexé 0 ou indexé 1);
• Entrer n, sortir n premiers éléments de la séquence;
• N'entrez rien, indiquez la suite de nombres infinis que vous pouvez prendre l'un après l'autre;

Règle

• Votre programme doit au moins prendre en charge les 1000 premiers éléments.
• Vous pouvez choisir de produire des décimales ou des fractions (paire intégrée, paire entière, chaînes) à votre guise;
  • Les entrées / sorties sous forme de chiffres binaires ne sont pas autorisées dans cette question;
• C'est le code-golf , les codes les plus courts gagnent;
• Lacunes standard interdites.

Testcases

input output
1     1/2     0.5
2     1/4     0.25
3     3/4     0.75
4     1/8     0.125
10    5/16    0.3125
100   73/128  0.5703125
511   511/512 0.998046875
512   1/1024  0.0009765625

Ces exemples sont basés sur une séquence indexée par 0, le 0 initial étant inclus. Vous auriez besoin d'ajuster l'entrée pour adapter votre solution.

Lire la suite

• OEIS A006257
  • Problème de Josèphe: . (Anciennement M2216)$a_{2n} = 2a_n-1, a_{2n+1} = 2a_n+1$
  • 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
• OEIS A062383
  • $a_0 = 1$ : pour , ou .$n>0$$a_n = 2^{\lfloor log_2n+1 \rfloor}$$a_n = 2a_{\lfloor \frac{n}{2} \rfloor}$
  • 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...

• A006257 (n) / A062383 (n) = (0, 0,1, 0,01, 0,11, 0,001, ...) énumère toutes les fractions binaires de l'intervalle unitaire [0, 1). - Fredrik Johansson, 14 août 2006

Haskell , 25 octets

pred.until(<2)(/2).(+0.5)

Essayez-le en ligne!

Sorties décimales, index unique sans le terme zéro initial.

Ajoute 0,5 à l'entrée, puis divise par deux jusqu'à ce que le résultat soit inférieur à 2, puis soustrait 1. L'utilisation d'une expression sans points permet de gagner 1 octet sur

f n=until(<2)(/2)(n+0.5)-1

Java 10, 68 64 octets

Essayez d'abord le code golf!

Option 1: trouver le n- ième élément (indexé 1)

-4 octets grâce à @ Kevin Cruijssen

n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);}

Il s'agit d'une méthode anonyme qui trouve le n- ième terme en supprimant le bit le plus significatif de n , en le doublant et en en ajoutant un, puis en le divisant par la puissance immédiatement supérieure de 2.

Essayez-le en ligne!

Procédure pas à pas du code:

n->{                      // builds anonymous function with input n
int x=0;                  // stores floor of log(n) (base 2) for most significant digit
for(;n>>++x!=1;);         // calculates floor of log(n) by counting right shifts until 1
return((~(1<<x)&n)        // removes most significant digit of n
*2.+1)                     // multiplies 2 and adds 1 to get the odd numerator
/(1<<x+1);}               // divides by the next highest power of 2 and returns`

Va modifier s'il est nécessaire d'imprimer la valeur finale au lieu de la renvoyer.

MathGolf , 5 4 octets

╫\╨]

Essayez-le en ligne!

A quoi ça ressemblerait si l'opérateur travaillait correctement

╫\)╨]   (")" adds 1 to TOS, making rounding behave as expected)

Essayez-le en ligne!

Explication

╫     Left-rotate all bits in input
 \    Swap top two elements on stack, pushing the input to the top
  ╨   Round up to nearest power of 2
   ]  Wrap in array (just for pretty printing)

Je me suis inspiré de cette question pour résoudre le problème, ma "propre" solution se situant autour de 10 à 12 octets, je pense.

J'avais eu l'intention de renvoyer le numéro à la puissance 2 la plus proche, s'il s'agissait d'un nombre de deux, mais en raison d'une erreur, il arrondit à la puissance suivante de deux (par exemple 4 -> 8 au lieu de 4 -> 4 ). Cela devra être corrigé plus tard, mais maintenant cela me sauve un octet.

Java 10, 89 85 70 69 68 octets

v->{for(float j,t=2;;t*=2)for(j=1;j<t;j+=2)System.out.println(j/t);}

Port de la réponse 05AB1E de @Emigma , affiche également les nombres décimaux indéfiniment.
-15 octets grâce à @Arnauld .

Essayez-le en ligne.

Explication:

v->{                      // Method with empty unused parameter and no return-type
  for(float j,t=2;;       //  Loop `t` from 2 upwards indefinitely,
                   t*=2)  //  doubling `t` after every iteration
    for(j=1;j<t;          //   Inner loop `j` in the range [1, `t`),
                j+=2)     //   in steps of 2 (so only the odd numbers)
      System.out.println( //    Print with trailing new-line:
        j/t);}            //     `j` divided by `t`

Perl 6 , 19 octets

{($_+.5)/2**.msb-1}

Essayez-le en ligne!

Python 3 , 33 octets

lambda n:(8*n+4)/2**len(bin(n))-1

Essayez-le en ligne!

Sorties décimales, index unique sans le terme zéro initial.

Java (JDK 10) , 30 octets

n->(n+.5)/n.highestOneBit(n)-1

Essayez-le en ligne!

Renvoie le n ^ième élément de la séquence.

Cette réponse est à l'origine une succession de parcours de la réponse Java de TCFP . À la fin, les golfs ne ressemblaient plus à la réponse initiale (bien que les calculs fussent les mêmes), alors j'ai décidé de les publier séparément, au lieu de simplement commenter la réponse du PFCT. Donc, si vous aimez cette réponse, augmentez la réponse de TCFP également! ;-)

Les golfs intermédiaires étaient:

n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);} // 64 bytes (TCFP's answer when I started golfing)
n->{int x=0;for(;n>>++x!=1;);x=1<<x;return((~x&n)*2.+1)/x/2;}    // 61 bytes
n->{int x=n.highestOneBit(n);return((~x&n)*2.+1)/x/2;}           // 54 bytes
n->{int x=n.highestOneBit(n);return((~x&n)+.5)/x;}               // 50 bytes
n->((n&~(n=n.highestOneBit(n)))+.5)/n                            // 37 bytes
n->(n-(n=n.highestOneBit(n))+.5)/n                               // 34 bytes
n->(n+.5)/n.highestOneBit(n)-1                                   // 30 bytes, current score

05AB1E , 11 8 octets

3 octets sauvés grâce à Kevin Cruijssen .

∞oDÅÉs/˜

Essayez-le en ligne!

Explication

∞         # start an infinite list [1...
 o        # calculate 2**N
  D       # duplicate
   ÅÉ     # get a list of odd numbers up to 2**N
     s/   # divide each by 2**N
       ˜  # flatten

Gelée , 9 octets

Bṙ1Ḅ,æċ2$

Essayez-le en ligne!

PowerShell , 40 octets

for($i=2;;$i*=2){1..$i|?{$_%2}|%{$_/$i}}

Essayez-le en ligne!

Affiche la séquence infinie sous forme de valeurs décimales. Compte tenu des limitations linguistiques, rencontrera éventuellement des problèmes de précision, mais gère facilement les 1000 premières entrées.

Commence par régler $i=2, puis entre dans une forboucle. À chaque itération, nous construisons une plage 1..$iet extrayons les valeurs impaires avec |?{$_%2}. Ceux-ci sont introduits dans leur propre boucle interne, où nous divisons chacun pour obtenir la décimale |%{$_/$i}. Ceux-ci sont laissés sur le pipeline et sortent lorsque le pipeline est vidé après chaque foritération. Chaque itération nous incrémenter simplement $ipar $i*=2pour obtenir le prochain go-round.

Haskell, 35 32 octets

Edit: -3 octets grâce à @ Delfad0r.

[(y,2^x)|x<-[1..],y<-[1,3..2^x]]

C'est une liste infinie de paires d'entiers.

Essayez-le en ligne!

Haskell , 40 octets

s=(1,2):[(i*2+u,j*2)|(i,j)<-s,u<-[-1,1]]

Essayez-le en ligne!

Séquence infinie sous forme de paires d'entiers (à partir de (1,2)).

Un peu plus long que la réponse de @ nimi , mais l'approche est complètement différente, j'ai donc décidé de le poster quand même.

Cette solution est basée sur l'observation suivante.

• $\frac{i}{j}$$\left\{\frac{2i-1}{2j},\frac{2i+1}{2j}\right\}$ $$\left\{\left\{\frac{1}{4},\frac{3}{4}\right\},\left\{\frac{1}{8},\frac{3}{8}\right\},\left\{\frac{5}{8},\frac{7}{8}\right\},\left\{\frac{1}{16},\frac{3}{16}\right\},\ldots\right\}$$
• $$\left\{\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\}$$
• $\frac{1}{2}$ $$\left\{\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\}$$

Remarquez comment vous revenez à la séquence avec laquelle vous avez commencé!

La solution exploite ce fait (avec la paresse de Haskell) pour calculer la séquence s.

Python 2 - 68 66 octets

-2 octets grâce à Kevin

from math import*
def g(n):a=2**floor(log(n,2));print(n-a)*2+1,2*a

Essayez-le en ligne!

Python 3 , 53 51 octets

• Sauvé deux octets grâce à mypetlion ; réutiliser les paramètres par défaut pour réinitialiser n.

def f(m=2,n=1):n<m and print(n/m)&f(m,2+n)or f(m+m)

Essayez-le en ligne!

R , 42 octets

function(n)c(y<-2^(log2(n)%/%1)*2,2*n-y+1)

Essayez-le en ligne!

Denominator,Numerator$\begin{equation}N = 2*\left(n-2^{\lfloor \log_2(n)\rfloor}\right)+1\end{equation}$$\begin{equation}D = 2^{\lfloor \log_2(n)\rfloor+1}\end{equation}$

Raquette , 92 à 91 octets

(define(f k(m 2)(n 1))(if(> k 0)(if(=(+ n 1)m)(f(- k 1)(+ m m))(f(- k 1)m(+ n 2)))(/ n m)))

Essayez-le en ligne!

• Sauvegardé un octet grâce à Giuseppe - suppression des espaces superflus.

MATL , 8 octets

BnWGEy-Q

Essayez-le en ligne!

Renvoie Numérateur, puis Dénominateur. Utilise la même méthode que ma réponse R , bien que ce soit un peu plus efficace.

Explication, avec entrée 5:

           # implicit input 5
B          # convert to array of bits
           # STACK: [[1 0 1]]
n          # length (place of Most Significant Bit)
           # STACK: [3]
W          # elementwise raise 2^x
           # STACK: [8]
G          # paste input
           # STACK: [8, 5]
E          # double
           # STACK: [8, 10]
y          # copy from below
           # STACK: [8, 10, 8]
-          # subtract
           # STACK: [8, 2]
Q          # increment
           # STACK: [8, 3]
           # implicit end of program, display stack contents

Langage de programmation Shakespeare , 426 octets

,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You be the sum ofyou a cat.Ford:You cat.Scene V:.Ford:Is twice you nicer I?If solet usScene X.You be twice you.Let usScene V.Scene X:.Ford:Remember twice you.You be the sum oftwice the remainder of the quotient betweenI you a cat.Open heart.You big big big big big cat.Speak thy.Recall.Open heart.You be twice the sum ofa cat a big big cat.Speak thy.Let usAct I.

Essayez-le en ligne!

Affiche la séquence indéfiniment sous la forme de deux nombres séparés par un espace, chaque élément étant séparé par une nouvelle ligne.

Python 2 , 44 octets

def f(n):m=2**len(bin(n))/4;return 2*n-m+1,m

Essayez-le en ligne!

La fonction retourne un tuple de (numérateur, dénominateur). Une entrée de 0 n'est pas gérée (c'était optionnel).

Excel 48 28 octets

Économisé 20 octets (!) Grâce à tsh

=(A1+0.5)/2^INT(LOG(A1,2))-1

= MOD (A1 + 0,5,2 ^ (INT (LOG (A1,2))))) / 2 ^ INT (LOG (A1,2))

Suppose la valeur en A1, la sortie est en décimal. Si vous souhaitez que la sortie soit sous forme de fraction, vous pouvez créer un format personnalisé pour la cellule de sortie sous la forme "0 / ### 0" et l'afficher sous forme de fraction.

Explication: Difficile à expliquer car il existe un raccourci pour accéder à cette formule. Fondamentalement, le numérateur est un décalage de bit à gauche de l'entrée et le dénominateur est la puissance suivante de 2 supérieure au nombre d'entrée.

J'ai initialement commencé avec les fonctions intégrées d'Excel pour BITLSHIFT et BITRSHIFT, mais elles déplacent les 48 bits entiers, ce qui n'est pas ce que vous voulez. Les fonctions DEC2BIN (et BIN2DEC) ont une limite de -512 à 511 (10 bits), donc cela ne fonctionnerait pas. Au lieu de cela, je devais reconstruire le nombre avec un module du nombre original, puis deux fois, puis ajouter 1 (puisque le chiffre de gauche serait toujours 1 avant un décalage).

=MOD(A1                        Use MOD for finding what the right digits are
       +0.5                    this will later add the left "1" to the right digits
           ,2^INT(LOG(A1,2)))) Take Log base 2 number of digits on the right
                               this creates the numerator divided by 2 (explained later)
/ 2^INT(LOG(A1,2))             The denominator should be 2^ (Log2 + 1) but instead of 
                               adding a 1 here, we cause the numerator to be divided by 2 instead
                               This gives us a fraction.  In the numerator, we also added .5
                               instead of 1 so that we wouldn't need to divide it in both the
                               numerator and denominator
Then tsh showed how I could take the int/log out of the mod and remove it from numerator/denominator. 

Exemples:

C ++, 97 75 71 octets

-26 octets grâce à tsh, ceilingcat, Zacharý

float f(int i){float d=2,n=1;while(--i)n=d-n==1?d*=2,1:n+2;return n/d;}

Code de test:

std::cout << "1\t:\t" << f(1) << '\n';
std::cout << "2\t:\t" << f(2) << '\n';
std::cout << "3\t:\t" << f(3) << '\n';
std::cout << "4\t:\t" << f(4) << '\n';
std::cout << "10\t:\t" << f(10) << '\n';
std::cout << "100\t:\t" << f(100) << '\n';
std::cout << "511\t:\t" << f(511) << '\n';
std::cout << "512\t:\t" << f(512) << '\n';

C (gcc) , 63 octets

Aucune entrée, imprime une séquence infinie:

f(i,j){for(i=1,j=2;;i+=2,i>j&&(j*=2,i=1))printf("%d/%d ",i,j);}

Essayez-le en ligne!

JavaScript (ES6), 44 octets

Renvoie le $n$- terme, indexé 1.

f=(n,p=q=1)=>n?f(n-1,p<q-2?p+2:!!(q*=2)):p/q

Essayez-le en ligne!

Ruby , 42 octets

1.step{|i|(1..x=2**i).step(2){|j|p [j,x]}}

Essayez-le en ligne!

Imprime les paires entières indéfiniment, à partir de 1/2.

JavaScript (Node.js) , 30 octets

f=(n,d=.5)=>d>n?n/d:f(n-d,d*2)

Essayez-le en ligne! 0 indexé. Commencé comme port de ma réponse par lot, mais j’ai pu calculer en multiples de$\frac{1}{2}$ qui a sauvé plusieurs octets.

Ruby , 31 octets

->x{(2r*x+1)/2**x.bit_length-1}

Essayez-le en ligne!

> <> , 19 18 octets

En utilisant l’idée de xnor , fixée par Jo King, -1 octet en faisant un meilleur usage des miroirs et un autre -2 octets par Jo King car elle !était superflue et ;n’est pas requise.

2*1+\1-n
2:,2/?(

Essayez-le en ligne!

Wolfram Language (Mathematica) , 22 octets

2^Mod[Log2[2#+1],1]-1&

Essayez-le en ligne!

APL (Dyalog Unicode) , 15 octets

1-⍨.5∘+÷2*∘⌊2⍟⊢

Essayez-le en ligne!

Préfixe anonyme lambda.

Merci à Adám pour 4 octets et à Cows Quack pour 2 octets.

Comment:

1-⍨.5∘+÷2*∘⌊2⍟⊢ ⍝ Anonymous lambda, argument ⍵ → 10
            2⍟⊢ ⍝ Log (⍟) of ⍵ in base 2. 2⍟10 → 3.32192809489...
           ⌊     ⍝ Floor. ⌊3.32192809489... → 3
        2*∘      ⍝ Take that power of 2. 2³ → 8
       ÷         ⍝ Use that as denominator
   .5∘+          ⍝ ⍵ + 0.5 → 10.5. Using that as numerator: 10.5÷8 → 1.3125
1-⍨              ⍝ Swap the arguments (⍨), then subtract. 1-⍨1.3125 → 1.3125-1 → 0.3125

C # (.NET Core) , 69 octets

a=>{int b=1,c=2;while(a-->1){b+=2;if(b>c){b=1;c*=2;}}return b+"/"+c;}

Essayez-le en ligne!

Ungolfed:

a=> {
    int b = 1, c = 2;   // initialize numerator (b) and denominator (c)
    while (a-- > 1)     // while a decrements to 1
    {
        b += 2;         // add 2 to b
        if (b > c)      // if b is greater than c:
        {
            b = 1;      // reset numerator to 1
            c *= 2;     // double denominator
        }
    }
    return b + "/" + c; // return fraction as string
}