Half, Half Half, and, Half Consider the following number sequence:


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


It enumerates all binary fractions in the unit interval \$ [0, 1) \$.

(To make this challenge easier, the first element is optional: You may skip it and consider the sequence starts with 1/2.)

Task

Write a program (complete program or a function) which...

Choose one of these behaviors:


Input n, output nth element of the sequence (0-indexed or 1-indexed);
Input n, output first n elements of the sequence;
Input nothing, output the infinite number sequence which you can take from one by one;


Rule


Your program should at least support first 1000 items;
You may choose to output decimals, or fractions (built-in, integer pair, strings) as you like;


Input / Output as binary digits is not allowed in this question;

This is code-golf, shortest codes win;
Standard loopholes disallowed.


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


These examples are based on 0-indexed sequence with the leading 0 included. You would need to adjust the input for fitting your solution.

Read More


OEIS A006257


Josephus problem: \$ a_{2n} = 2a_n-1, a_{2n+1} = 2a_n+1 \$. (Formerly M2216)
0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...

OEIS A062383


\$ a_0 = 1 \$: for \$ n&gt;0 \$, \$ a_n = 2^{\lfloor log_2n+1 \rfloor} \$ or \$ 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, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006
Haskell, 25 bytes



pred.until(&lt;2)(/2).(+0.5)


Try it online!

Outputs decimals, one-indexed without the initial zero term. 

Adds 0.5 to the input, then halves until the results is below 2, then subtracts 1. Using a pointfree expression saves 1 bytes over

f n=until(&lt;2)(/2)(n+0.5)-1