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

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.

• 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

• "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.)? – Kevin Cruijssen Sep 14 at 15:14
• Can I output a list of strings? e.g. "1/2" "1/4" "1/8"... – Barranka Sep 14 at 15:21
• @KevinCruijssen Infinite list is fine as long as you can take n elements from it later. – tsh Sep 15 at 5:45
• @Barranka I think it is acceptable. That is nothing different to print fractions to stdout. – tsh Sep 15 at 5:46
• 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? – Peter Cordes 2 days ago

pred.until(<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(<2)(/2)(n+0.5)-1


Java 10, 68 64 bytes

First try at code golf!

Option 1: find the n-th element (1-indexed)

-4 bytes thanks to @Kevin Cruijssen

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


This is an anonymous method that finds the n-th term by removing the most significant bit from n, doubling it and adding one, then dividing by the next highest power of 2.

Try it online!

Code walkthrough:

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


Will edit if it's necessary to print the final value instead of returning it.

New contributor
TCFP is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Welcome to PPCG, good to have you with us :) – Shaggy Sep 14 at 19:39
• Hi, welcome to PPCG! Great first answer, +1 from me. Currently it's the same byte-count as my Java answer, but you can still golf some parts of your answer to make it shorter than mine: The {} after the loop can be a ; instead; you can remove the space after the return; 2.0 can be 2.; And changing the n>>x!=1;x++, 1<<x, and 1<<x+1 to n>>x++!=1;, 1<<x-1, 1<<x respectively also saves a byte. Try it online: 64 bytes. Enjoy your stay! – Kevin Cruijssen Sep 14 at 20:43
• Oh, and if you haven't seen it yet: Tips for golfing in Java and Tips for golfing in <all languages> are both pretty interesting to read through. :) – Kevin Cruijssen Sep 14 at 20:44
• See my 30 bytes answer, originally based on yours but golfed and golfed and golfed. – Olivier Grégoire 2 days ago

Java 10, 89857069 68 bytes

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


Port of @Emigma's 05AB1E answer, so outputs decimals indefinitely as well.
-15 bytes thanks to @Arnauld.

Try it online.

Explanation:

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

• How often can I say that I half your byte count? Well, I think this is the first time ;-) – Olivier Grégoire 2 days ago
• @OlivierGrégoire Dang, now that is an impressive Java answer. :) I saw your 37-byte version as comment on TCFP's answer, but you even stripped off more bytes. It looks so extremely simple now in your 30-byte version, but it's still ingenious how you've golfed it from the initial version. Well done! – Kevin Cruijssen 2 days ago

MathGolf, 5 bytes

k╫k╨]


Assuming implicit input (does not work on TIO currently)

_╫\╨]   ("_" duplicates TOS, "\" swaps the top two elements)


How it would look like with the operator working correctly

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


Try it online!

Explanation

k      Read input as int
╫     Left-rotate all bits in input
╨   Round up to nearest power of 2
]  Wrap in array (just for pretty printing)


I took my inspiration from this question to solve the problem, my "own" solution was around 10-12 bytes I think.

I had intended for the round up to closest power of 2 to return the number itself if it was a number of two, but due to a mistake it rounds to the next power of two (e.g. 4 -> 8 instead of 4 -> 4). This will have to be fixed later, but now it saves me one byte.

• I don't know MathGolf but if the ] serves no other purpose than formatting the output, I'd say you don't need to include it in your byte count. – Shaggy Sep 14 at 17:17
• I was unsure about it. Since the stack is printed on output as a joined string, it outputs a stack with the numbers 1 and 2 as 12. If that still counts I'll remove a byte – maxb Sep 14 at 17:21
• I think you should leave it in. It sometimes saves a byte to output the stack as one string, sometimes it will cost you a byte. – H.PWiz Sep 14 at 17:40
• @H.PWiz that was my original thinking, since it seems fair to use the strengths of your language. Some languages only print the top of the stack when finished, some print it as a list. Usually it's a 1 byte difference, but it's part of the challenge. – maxb Sep 14 at 18:52

{($_+.5)/2**.msb-1}  Try it online! 05AB1E, 11 8 bytes Saved 3 bytes thanks to Kevin Cruijssen. ∞oDÅÉs/˜  Try it online! Explanation ∞ # 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  • -1 byte by using ∞ (infinite list starting at 1): ∞oεDÅÉs/}˜ – Kevin Cruijssen Sep 14 at 15:12 • @KevinCruijssen: Cool! That's a command I hadn't seen before. Thanks :) – Emigna Sep 15 at 8:55 • Ah, and nice way of saving two more bytes due to the implicit mapping.. Hadn't even thought about that, lol.. – Kevin Cruijssen Sep 15 at 9:41 • :O how is this possible. You condensed the ~2 page question into 8 bytes. – Cullub 2 days ago Jelly, 9 bytes Bṙ1Ḅ,æċ2$


Try it online!

PowerShell, 40 bytes

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


Try it online!

Outputs the infinite sequence as decimal values. Given language limitations, will eventually run into precision problems, but easily handles the first 1000 entries.

Starts by setting $i=2, then enters a for loop. Each iteration, we construct a range from 1..$i and pull out the odd values with |?{$_%2}. Those are fed into their own inner loop, where we divide each to get the decimal |%{$_/$i}. Those are left on the pipeline and output when the pipeline is flushed after every for iteration. Each iteration we're simply incrementing $i by $i*=2 to get the next go-round. Python 3, 33 bytes lambda n:(8*n+4)/2**len(bin(n))-1  Try it online! Outputs decimals, one-indexed without the initial zero term. Haskell, 35 32 bytes Edit: -3 bytes thanks to @Delfad0r. [(y,2^x)|x<-[1..],y<-[1,3..2^x]]  This is an infinite list of integer pairs. Try it online! Python 2 - 68 66 bytes -2 bytes thanks to Kevin from math import* def g(n):a=2**floor(log(n,2));print(n-a)*2+1,2*a  Try it Online! • You can golf 1 byte by changing return 2*(n-a) to return(n-a)*2. And you could save an additional byte by using Python 2 instead of 3, so return can be print (with parenthesis). – Kevin Cruijssen Sep 14 at 15:27 • @KevinCruijssen For someone who doesn't use Python, you certainly are a better Python programmer than me. – Rushabh Mehta Sep 14 at 15:27 • Hehe. :D Simple things like this comes with experience I guess. I'm on this site for about two years now I think (EDIT: Since April 2016). I sometimes even suggests things to golf for answers that are written in languages I had never seen before.. Some basic things work in most languages. For example, last week I suggested a golf for a T-SQL answer, and I once suggested a golf in a Red answer. xD – Kevin Cruijssen Sep 14 at 15:33 • 44 bytes using len and bin instead of log. – ovs Sep 15 at 6:16 • @ovs 42 bytes. – Jonathan Frech Sep 15 at 10:54 Python 3, 53 51 bytes • Saved two bytes thanks to mypetlion; reusing default parameters to reset n. def f(m=2,n=1):n<m and print(n/m)&f(m,2+n)or f(m+m)  Try it online! • Swap the parameters to save 2 bytes: def f(m=2,n=1):n<m and print(n/m)&f(m,n+2)or f(m+m) – mypetlion Sep 14 at 16:14 • @mypetlion Cool, thank you! – Jonathan Frech Sep 14 at 16:17 Haskell, 40 bytes s=(1,2):[(i*2+u,j*2)|(i,j)<-s,u<-[-1,1]]  Try it online! Infinite sequence as pairs of integers (starting from (0,0)). Quite a bit longer than @nimi's answer, but the approach is completely different, so I decided to post it anyway. This solution is based on the following observation. Consider the infinite sequence $$\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\}$$ and apply the following steps. • Replace every number $\frac{i}{j}$ in the sequence with the list $\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\}$$ • Join all the lists into a single sequence: $$\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\}$$ • Add $\frac{1}{2}$ at the beginning of the sequence: $$\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\}$$ Notice how you get back to the sequence you started with! The solution exploits this fact (together with Haskell's laziness) to compute the sequence s. Java (JDK 10), 30 bytes n->(n+.5)/n.highestOneBit(n)-1  Try it online! Returns the nth item in the sequence. This answer is originally a succession of golfs of TCFP's Java answer. In the end, the golfs didn't look like the original answer anymore (though the math used is the same) so I decided to post the golfs as a separate answer instead of simply commenting on the TCFP's answer. So if you like this answer, go upvote TCFP's answer as well! ;-) Intermediate golfs were: 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  • And I was sitting here thinking my answer was as short as I could make it, you come along and cut it by more than half! Amazing stuff, definitely deserves a +1 from me. – TCFP 2 days ago • @TCFP It was an iterative process over the span of several hours. I actually posted each intermediate golfing as a comment to your answer, but deleted them as I found better golfs. Thanks for the praise ;-) – Olivier Grégoire 2 days ago Racket, 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)))  Try it online! • Saved a byte thanks to Giuseppe -- removing superfluous whitespace. MATL, 8 bytes BnWGEy-Q  Try it online! Returns Numerator, then Denominator. Uses the same method as my R answer, although it's a bit more efficient. Explanation, with input 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  Python 2, 44 bytes def f(n):m=2**len(bin(n))/4;return 2*n-m+1,m  Try it online! Function returns a tuple of (numerator, denominator). An input of 0 is not handled (it was optional). • return 2*n-m+1,m can be print-~n+n-m,m to save 2 bytes. – Kevin Cruijssen Sep 14 at 20:56 R, 42 bytes function(n)c(y<-2^(log2(n)%/%1)*2,2*n-y+1)  Try it online! Returns a pair Denominator,Numerator. Uses the formula $$$N = 2*\left(n-2^{\lfloor \log_2(n)\rfloor}\right)+1$$$ from the Josephus sequence and $$$D = 2^{\lfloor \log_2(n)\rfloor+1}$$$ from the other sequence. Happily we are able to re-use the denominator as the two formulas have quite a lot in common! C (gcc), 63 bytes No input, prints infinite sequence: f(i,j){for(i=1,j=2;;i+=2,i>j&&(j*=2,i=1))printf("%d/%d ",i,j);}  Try it online! JavaScript (ES6), 44 bytes Returns the $n$-th term, 1-indexed. f=(n,p=q=1)=>n?f(n-1,p<q-2?p+2:!!(q*=2)):p/q  Try it online! Ruby, 42 bytes 1.step{|i|(1..x=2**i).step(2){|j|p [j,x]}}  Try it online! Prints integer pairs infinitely, starting from 1/2. JavaScript (Node.js), 30 bytes f=(n,d=.5)=>d>n?n/d:f(n-d,d*2)  Try it online! 0-indexed. Started out as a port of my Batch answer but I was able to calculate in multiples of $\frac{1}{2}$ which saved several bytes. Shakespeare Programming Language, 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.  Try it online! Outputs the sequence infinitely as both numbers separated by a space, with each item being separated by a newline. New contributor JosiahRyanW is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct. • Love it. Lol You be twice the sum of a cat – Cullub 2 days ago • Actually, it's "twice the sum ofa cat a big big cat" (i.e. 10 for some reason). – JosiahRyanW 2 days ago ><>, 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! • 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 – Jo King yesterday • Thanks! I also managed to remove another byte by reusing the mirrors. – PidgeyUsedGust yesterday • Why did you invert the condition? 16 bytes – Jo King yesterday • Didn't notice that it would continue the loop. Are we allowed to not properly finish? – PidgeyUsedGust yesterday • Yeah, terminating with an error is fine as long as the OP doesn't specify otherwise – Jo King yesterday Excel 48 28 Bytes Saved 20 bytes (!) thanks to tsh =(A1+0.5)/2^INT(LOG(A1,2))-1  =MOD(A1+0.5,2^(INT(LOG(A1,2))))/2^INT(LOG(A1,2)) Assumes value in A1, output is in decimal. If you want the output to be in fraction, you can create a custom format for the output cell as "0/###0" and it will show it as fraction. Explanation: Difficult to explain, since there is a shortcut taken to get to this formula. Basically the numerator is a bit shift left of the input, and the denominator is the next power of 2 higher than the number input. I originally started with Excel built in functions for BITLSHIFT and BITRSHIFT, but they will shift the entire 48 bits which is not what you want. The functions DEC2BIN (and BIN2DEC) have a limit of -512 to 511 (10 bits) so this wouldn't work. Instead I had to rebuild the number with a modulus of the original number, then times two, then add 1 (since the left digit would always be 1 before a shift). =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.  Examples: • What about =(A1+0.5)/2^INT(LOG(A1,2))-1? – tsh yesterday 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!) 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. 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. 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. 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!