Half, Half Half, and, Half

Question

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

Answer 1

><>, 19 18 bytes

Using xnor's idea, fixed by Jo King, -1 byte by making better use of the mirrors and another -2 bytes by Jo King because the ! was superfluous and ; is not required.

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

Try it online!

Answer 2

APL (Dyalog Unicode), 15 bytes

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

Try it online!

Anonymous prefix lambda.

Thanks to Adám for 4 bytes and to Cows quack for 2 bytes.

How:

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

Answer 3

Stax, 8 bytes

▀`Ö²╬─}t

Run and debug it

This program uses stax's rational type. It takes a 1-based integer index as input, and produces that sequence element.

Unpacked, ungolfed, and commented, it looks like this.

Hc  double the input and copy it
:GY unset all but the highest bit, and store in register Y
-^  subtract (leaving all the other bits), then increment
yu* push the value in register Y, then multiply by its reciprocal

Run this one

Answer 4

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;}

Try it 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
}

Answer 5

x86 machine code, 36 bytes

00000000: 4389 de46 5653 6800 0000 00e8 fcff ffff  C..FVSh.........
00000010: 83c3 0239 f37e edd1 e631 db43 ebe6 2564  ...9.~...1.C..%d
00000020: 2f25 6420                                /%d 

Prints the sequence infinitely.

The hexdump is unlinked, e.g. the address for printf is a placeholder.

Assembly:

section .text
	global func
	extern printf
func:
	inc ebx			;set numerator to 1
	mov esi, ebx
	inc esi			;set denominator to 2
	loop:
		push esi
		push ebx
		push fmt
		call printf
		add ebx, 2	;increment numerator by 2
		cmp ebx, esi
		jle loop	;if numerator<denominator (eg ebx/esi<1), repeat loop
		shl esi, 1	;double the denominator
		xor ebx, ebx
		inc ebx		;reset numerator to 1
		jmp loop
section .data
	fmt db '%d/%d '

Try it online!

Answer 6

Uiua 0.11.0, 11 bytes

Accepts N, returns the numerator of the Nth term first, then the denominator.

⟜◿⍜ₙ⌊2.+1×2

Try it out!

Not only does it work on scalars, it works on arrays! In other words, it's pervasive.

F ← ⟜◿⍜ₙ⌊2.+1×2

F 19
### 7  
### 32 
F [13 6 9]
### [11 5 3]  
### [16 8 16] 

Answer 7

Zephyr, 82 bytes

set d to 2
while 1=1
for n from 1 to d/2
print((2*n)-1)/d
next
set d to d*2
repeat

Try it online!

Iterate over denominators 2, 4, 8, 16, ... forever. For each d (e.g. 8), iterate n from 1 up to d/2 (e.g. 1, 2, 3, 4). The desired odd-number numerators are then 2*n-1. Zephyr's built-in rational numbers mean we just do the division and print the result.

(I really think more languages should have built-in rational numbers!)

Answer 8

Batch, 73 bytes

@set/an=%1*2,d=1
:l
@if %d% leq %1 set/an-=d,d*=2&goto l
@echo %n%/%d%

Outputs 0/1 for an input of 0. Explanation: n is the numerator and d is the denominator. d is doubled each time until it exceeds the input, and the previous value of d is subtracted from n as it goes. This is slightly golfier than calculating n=%1*2+1-d separately.

Answer 9

Appleseed, 76 bytes

(def s(lambda((d 2)(n 1))(if(> n d)(s(* d 2))(cons(list n d)(s d(+ n 2))))))

Defines a function s that, when called without arguments, returns an infinite list of (<numer> <denom>) pairs. Try it online!

Ungolfed

(def sequence
  (lambda ((denom 2) (numer 1))
    (if (less? denom numer)
      (sequence (* denom 2))
      (cons
        (list numer denom)
        (sequence denom (+ numer 2))))))

Same idea as Jonathan Frech's Python function (right down to the order of the default arguments being important), except here we cons each result onto the (infinite) recursive call instead of printing it.

Answer 10

Perl 5 -a, 53 bytes

map{say"$_/$.";--$F[0]||exit}grep$_%2,1..$.while$.*=2

Try it online!

1-indexed. First element is 1/2. Outputs the first n elements.

Answer 11

Perl 6, 38 bytes

(0,{(1,3...2**@_-1)X/2**@_}...*)>>.say

Try it online!

Outputs elements infinitely, starting from 0.

An infinite sequence itself ends up at 40 bytes

.5,{$/=.nude;($1-$0-1??$0+2!!.5)/$1}...*

Try it online!

Answer 12

Python 3, 71 bytes

n,d=0,1
for t in range(int(input())):
    n+=2
    if n>d:n=1;d*=2
print(n/d)

Index starts with 0 at 0.0 and 1 at 0.5 and so on.

Try it online!

Answer 13

APL(NARS), 30 chars, 60 bytes

{⍵=0:0⋄(1+2×⍵-2*k)÷2*1+k←⌊2⍟⍵}

test:

f←{⍵=0:0⋄(1+2×⍵-2*k)÷2*1+k←⌊2⍟⍵}
  f¨0 1 2 3 4 5 6 7 8
0 0.5 0.25 0.75 0.125 0.375 0.625 0.875 0.0625 
  f¨511 512  10023
0.998046875 0.0009765625 0.2235717773 
  

Answer 14

D, 66 bytes

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

Try it online!

Port of @HatsuPointerKun's C++ answer.

grumble Comma expressions are pretty worthless in D grumble

Answer 15

J, 20 bytes

(>:@+:@#.@}.,2^#)@#:

This verb take n and gives us the nth number in the list. n = 1 produces 1/2, etc...

explanation

(>:@+:@#.@}. , 2 ^ #)@#:
                     @#:  NB. The arg as list of binary digits, feed that to...
             ,            NB. the concatenation of... (first doing the left side)
         @}.              NB. remove the highest order bit and...
      @#.                 NB. convert back to decimal and...
   @+:                    NB. double it and...
 >:                       NB. add one (now we have the numerator)
               2 ^        NB. (now doing the right side) 2 raised to the...
                   #      NB. number of binary digits (the denominator)

Try it online!

Answer 16

T-SQL, 84 bytes

Original attempt (174 bytes)
Second attempt (84 bytes) (working version)

Here uses the closed form$$\frac{x+0.5}{2^{\lfloor\log_2x\rfloor}}-1$$ Code:

DECLARE @a INT
SET @a = ##a##
SELECT (1.0*@a+0.5)/POWER(2,FLOOR(LOG(1.0*@a)/LOG(2)))-1

My original attempt at this involved using the closed form$$\frac{\operatorname{mod}\left(x+0.5,2^{\lfloor\log_2(x)\rfloor}\right)}{2^{\lfloor\log_2(x)\rfloor}}\\=\frac{x+0.5-2^{\lfloor\log_2(x)\rfloor}\left\lfloor(x+0.5)/2^{\lfloor\log_2(x)\rfloor}\right\rfloor}{2^{\lfloor\log_2(x)\rfloor}}\\=\frac{x+0.5-2^{\lfloor\ln x/\ln2\rfloor}\lfloor(x+0.5)/2^{\lfloor\ln x/\ln2\rfloor}\rfloor}{2^{\lfloor\ln x/\ln2\rfloor}}$$but I highly doubt that this would have qualified since there was really bad rounding error that made it only spit out 6 decimal places.