Considere a seguinte sequência numérica:

$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$

Enumera todas as frações binárias no intervalo de unidades .$[0, 1)$

(Para facilitar esse desafio, o primeiro elemento é opcional: você pode ignorá-lo e considerar que a sequência começa com 1/2.)

Tarefa

Escreva um programa (programa completo ou função) que ...

Escolha um destes comportamentos:

• Entrada n, elemento de saída enésimo da sequência (indexado 0 ou indexado 1);
• Entrada n, gera os primeiros n elementos da sequência;
• Não introduza nada, produza a sequência numérica infinita que pode ser tirada uma a uma;

Regra

• Seu programa deve pelo menos suportar os primeiros 1000 itens;
• Você pode optar por imprimir decimais ou frações (interno, par inteiro, seqüências de caracteres) como desejar;
  • Entrada / Saída como dígitos binários não é permitida nesta pergunta;
• Este é o código-golfe , os códigos mais curtos vencem;
• Falhas padrão não permitidas.

Casos de teste

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

Esses exemplos são baseados na sequência indexada em 0, com o 0 inicial incluído. Você precisaria ajustar a entrada para ajustar sua solução.

consulte Mais informação

• OEIS A006257
  • Problema de Josefo: . (Anteriormente 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$ : para , 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, 32, 32, 32, ...

• A006257 (n) / A062383 (n) = (0, 0,1, 0,01, 0,11, 0,001, ...) enumera todas as frações binárias no intervalo de unidade [0, 1). - Fredrik Johansson, 14 de agosto de 2006

Haskell , 25 bytes

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

Experimente online!

Gera decimais, um indexado sem o termo zero inicial.

Adiciona 0,5 à entrada e, em seguida, reduz pela metade até que os resultados estejam abaixo de 2 e subtrai 1. O uso de uma expressão sem pontos salva 1 bytes sobre

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

Java 10, 68 64 bytes

Primeira tentativa no código de golfe!

Opção 1: encontre o n- ésimo elemento (indexado 1)

-4 bytes graças a @Kevin Cruijssen

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

Este é um método anônimo que encontra o n- ésimo termo removendo o bit mais significativo de n , dobrando-o e adicionando um, depois dividindo pela próxima potência mais alta de 2.

Experimente online!

Passo a passo do código:

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`

Editará se for necessário imprimir o valor final em vez de retorná-lo.

MathGolf , 5 4 bytes

╫\╨]

Experimente online!

Como seria o funcionamento correto do operador

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

Experimente online!

Explicação

╫     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)

Tirei minha inspiração desta questão para resolver o problema, minha solução "própria" era de 10 a 12 bytes, eu acho.

Eu pretendia que o arredondamento até a potência mais próxima de 2 retornasse o número em si, se fosse um número de dois, mas, devido a um erro, ele arredonda para a próxima potência de dois (por exemplo, 4 -> 8 em vez de 4 -> 4 ) Isso terá que ser corrigido mais tarde, mas agora me salva um byte.

Java 10, 89 85 70 69 68 bytes

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

Porto de @Emigma resposta 05AB1E 's , por isso saídas decimais indefinidamente também.
-15 bytes graças a @Arnauld .

Experimente online.

Explicação:

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 bytes

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

Experimente online!

Python 3 , 33 bytes

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

Experimente online!

Gera decimais, um indexado sem o termo zero inicial.

Java (JDK 10) , 30 bytes

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

Experimente online!

Retorna o ^enésimo item na sequência.

Esta resposta é originalmente uma sucessão de campos de golfe da resposta Java do TCFP . No final, os campos não pareciam mais a resposta original (embora a matemática usada seja a mesma), então eu decidi postar os campos como uma resposta separada, em vez de simplesmente comentar a resposta do TCFP. Portanto, se você gosta desta resposta, suba também à resposta do TCFP ! ;-)

Os golfe intermediários foram:

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 bytes

Economizou 3 bytes graças a Kevin Cruijssen .

∞oDÅÉs/˜

Experimente online!

Explicação

∞         # 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éia , 9 bytes

Bṙ1Ḅ,æċ2$

Experimente online!

PowerShell , 40 bytes

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

Experimente online!

Produz a sequência infinita como valores decimais. Dadas as limitações de idioma, eventualmente ocorrerá problemas de precisão, mas lida facilmente com as primeiras 1000 entradas.

Inicia definindo $i=2e entra em um forloop. A cada iteração, construímos um intervalo 1..$ie extraímos os valores ímpares com |?{$_%2}. Esses são alimentados em seu próprio loop interno, onde dividimos cada um para obter o decimal |%{$_/$i}. Elas são deixadas no pipeline e produzidas quando o pipeline é liberado após cada foriteração. Cada iteração estamos simplesmente incrementar $ipor $i*=2para obter o próximo go-round.

Haskell, 35 32 bytes

Edit: -3 bytes graças a @ Delfad0r.

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

Esta é uma lista infinita de pares inteiros.

Experimente online!

Haskell , 40 bytes

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

Experimente online!

Sequência infinita como pares de números inteiros (a partir de (1,2)).

Um pouco mais do que a resposta de @ nimi , mas a abordagem é completamente diferente, então decidi publicá-la de qualquer maneira.

Esta solução é baseada na seguinte observação.

Considere a sequência infinita

• Substitua todos os números $\frac{i}{j}$ na sequência com a lista $\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\}$$
• Junte todas as listas em uma única sequência: $$\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\}$$
• Adicionar $\frac{1}{2}$ no início da sequência: $$\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\}$$

Observe como você volta à sequência em que começou!

A solução explora esse fato (junto com a preguiça de Haskell) para calcular a sequência s.

Python 2-68 66 bytes

-2 bytes graças a Kevin

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

Experimente Online!

Python 3 , 53 51 bytes

• Economizou dois bytes graças ao mypetlion ; reutilizando parâmetros padrão para redefinir n.

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

Experimente online!

R , 42 bytes

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

Experimente online!

Retorna um par Denominator,Numerator. Usa a fórmula $\begin{equation}N = 2*\left(n-2^{\lfloor \log_2(n)\rfloor}\right)+1\end{equation}$ da sequência Josephus e $\begin{equation}D = 2^{\lfloor \log_2(n)\rfloor+1}\end{equation}$da outra sequência. Felizmente, podemos reutilizar o denominador, pois as duas fórmulas têm muito em comum!

Raquete , 92 91 bytes

(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)))

Experimente online!

• Salvou um byte graças a Giuseppe - removendo espaços em branco supérfluos.

MATL , 8 bytes

BnWGEy-Q

Experimente online!

Retorna Numerador e Denominador. Usa o mesmo método da minha resposta R , embora seja um pouco mais eficiente.

Explicação, com entrada 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

Linguagem de programação de Shakespeare , 426 bytes

,.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.

Experimente online!

Produz a sequência infinitamente como os dois números separados por um espaço, com cada item sendo separado por uma nova linha.

Python 2 , 44 bytes

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

Experimente online!

A função retorna uma tupla de (numerador, denominador). Uma entrada de 0 não é manipulada (era opcional).

Excel 48 28 Bytes

Economizou 20 bytes (!) Graças a tsh

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

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

Assume o valor em A1, a saída é decimal. Se você deseja que a saída esteja na fração, é possível criar um formato personalizado para a célula de saída como "0 / ### 0" e ela será exibida como fração.

Explicação: Difícil de explicar, pois existe um atalho para chegar a essa fórmula. Basicamente, o numerador fica um deslocamento à esquerda da entrada e o denominador é a próxima potência 2 maior que a entrada numérica.

Inicialmente, comecei com as funções incorporadas do Excel para BITLSHIFT e BITRSHIFT, mas elas deslocam os 48 bits inteiros, o que não é o que você deseja. As funções DEC2BIN (e BIN2DEC) têm um limite de -512 a 511 (10 bits), portanto, isso não funcionaria. Em vez disso, tive que reconstruir o número com um módulo do número original, depois duas vezes e depois adicionar 1 (já que o dígito esquerdo sempre seria 1 antes de um turno).

=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. 

Exemplos:

C ++, 97 75 71 bytes

-26 bytes graças a 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;}

Código de teste:

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 bytes

Sem entrada, imprime sequência infinita:

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

Experimente online!

JavaScript (ES6), 44 bytes

Retorna o $n$terceiro termo, indexado em 1.

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

Experimente online!

Ruby , 42 bytes

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

Experimente online!

Imprime pares inteiros infinitamente, iniciando em 1/2.

JavaScript (Node.js) , 30 bytes

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

Experimente online! Indexado a 0. Começou como uma porta da minha resposta do Lote, mas consegui calcular em múltiplos de$\frac{1}{2}$ que salvou vários bytes.

Ruby , 31 bytes

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

Experimente online!

> <> , 19 18 bytes

Usando a idéia do xnor , corrigida por Jo King, -1 byte, fazendo melhor uso dos espelhos e outros -2 bytes por Jo King, porque !era supérfluo e; não é necessário.

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

Experimente online!

Wolfram Language (Mathematica) , 22 bytes

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

Experimente online!

APL (Dyalog Unicode) , 15 bytes

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

Experimente online!

Prefixo anônimo lambda.

Agradecimentos a Adám por 4 bytes e a Vacas charlatão por 2 bytes.

Quão:

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 bytes

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

Experimente online!

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
}