34
\$\begingroup\$

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

\$\endgroup\$
7
  • 4
    \$\begingroup\$ "Input nothing, output the infinite number sequence one by one" Does it have to be one-by-one, or are we also allowed to output an infinite list (possible in Haskell, Elixir, 05AB1E, etc.)? \$\endgroup\$ – Kevin Cruijssen Sep 14 '18 at 15:14
  • \$\begingroup\$ Can I output a list of strings? e.g. "1/2" "1/4" "1/8"... \$\endgroup\$ – Barranka Sep 14 '18 at 15:21
  • \$\begingroup\$ @KevinCruijssen Infinite list is fine as long as you can take n elements from it later. \$\endgroup\$ – tsh Sep 15 '18 at 5:45
  • \$\begingroup\$ @Barranka I think it is acceptable. That is nothing different to print fractions to stdout. \$\endgroup\$ – tsh Sep 15 '18 at 5:46
  • \$\begingroup\$ When you say Input / Output as binary numbers is not allowed, you mean we can't write a function that returns a pair if ints, or a double in a language / implementation where double uses IEEE binary64 format? I hope you don't mean was have to parse an ASCII string if we want to take an integer input? Normal integer types are binary in languages like C. Or do you mean the input/output can't be an array or string of integer or ASCII zeros/ones? \$\endgroup\$ – Peter Cordes Sep 17 '18 at 5:41

44 Answers 44

1
2
1
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ You should be checking if it is smaller than 2 first, otherwise the first element is -0.25. Fix for the same amount of bytes \$\endgroup\$ – Jo King Sep 17 '18 at 22:58
  • \$\begingroup\$ Thanks! I also managed to remove another byte by reusing the mirrors. \$\endgroup\$ – PidgeyUsedGust Sep 18 '18 at 8:23
  • \$\begingroup\$ Why did you invert the condition? 16 bytes \$\endgroup\$ – Jo King Sep 18 '18 at 8:27
  • \$\begingroup\$ Didn't notice that it would continue the loop. Are we allowed to not properly finish? \$\endgroup\$ – PidgeyUsedGust Sep 18 '18 at 8:29
  • \$\begingroup\$ Yeah, terminating with an error is fine as long as the OP doesn't specify otherwise \$\endgroup\$ – Jo King Sep 18 '18 at 8:30
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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 
  
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.