12
\$\begingroup\$

I have a cake shop that specialises in birthday cakes. The cakes that I sell must have candles placed in a circle. You would probably think I can just divide 360° by the number of candles, but the machine for placing candles is quite unique; it uses a list of numbers representing positions of candles, placing them one-by-one until it reaches the desired amount. Furthermore, it can only store numbers as a binary fraction of turns, ie. \$n/2^m\$ where \$\{n,m \in \Bbb Z^{0+} | n < m \}\$.

Since I want the candles placed as evenly as possible, I've devised a method for working out where to place each candle.

The first candle goes at position 0.
In order to balance the cake, the next goes at 1/2.
The next two candles go in the remaining gaps, so 1/4, 3/4.
The next four use the sequence so far to define the order. So 1/8, 5/8, 3/8, 7/8.
Ad infinitum.

To put it more generally:

$$ \begin{aligned} f(0) &= 0 \\ f(n) &= f(n - 2 ^{\lfloor \log_2{n} \rfloor}) + 2 ^ {-\lfloor \log_2{n} \rfloor - 1} \end{aligned} $$

Create for me a program or function to create this sequence.

My machine has a small hard drive (I mean really small), so the code should be as short as possible.

Output

The output should follow standard sequence output. That is, either output the entire sequence (print them one by one or return a list or generator representing the sequence), or given an index \$n\$ (0 or 1 indexed) return the \$n\$th entry or every entry up to the \$n\$th.

The entries can be either represented as a simplified fraction (numerator and denominator separated by /) or decimal (rounding errors are acceptable).

The first 64 terms as fractions are

0
1/2
1/4
3/4
1/8
5/8
3/8
7/8
1/16
9/16
5/16
13/16
3/16
11/16
7/16
15/16
1/32
17/32
9/32
25/32
5/32
21/32
13/32
29/32
3/32
19/32
11/32
27/32
7/32
23/32
15/32
31/32
1/64
33/64
17/64
49/64
9/64
41/64
25/64
57/64
5/64
37/64
21/64
53/64
13/64
45/64
29/64
61/64
3/64
35/64
19/64
51/64
11/64
43/64
27/64
59/64
7/64
39/64
23/64
55/64
15/64
47/64
31/64
63/64

and as decimal

0
0.5
0.25
0.75
0.125
0.625
0.375
0.875
0.0625
0.5625
0.3125
0.8125
0.1875
0.6875
0.4375
0.9375
0.03125
0.53125
0.28125
0.78125
0.15625
0.65625
0.40625
0.90625
0.09375
0.59375
0.34375
0.84375
0.21875
0.71875
0.46875
0.96875
0.015625
0.515625
0.265625
0.765625
0.140625
0.640625
0.390625
0.890625
0.078125
0.578125
0.328125
0.828125
0.203125
0.703125
0.453125
0.953125
0.046875
0.546875
0.296875
0.796875
0.171875
0.671875
0.421875
0.921875
0.109375
0.609375
0.359375
0.859375
0.234375
0.734375
0.484375
0.984375
Improve this question
\$\endgroup\$
9
  • 2
    \$\begingroup\$ It must follow this order, otherwise the challenge becomes too trivial! \$\endgroup\$
    – Matthew Jensen
    May 1, 2022 at 22:06
  • 2
    \$\begingroup\$ The numerator is A030101. \$\endgroup\$
    – Arnauld
    May 2, 2022 at 0:00
  • 3
    \$\begingroup\$ @Arnauld Nice, the denominator is A062383 \$\endgroup\$
    – Matthew Jensen
    May 2, 2022 at 0:16
  • 2
    \$\begingroup\$ Apparently this is also known as the binary van der Corput sequence. \$\endgroup\$
    – Neil
    May 2, 2022 at 11:39
  • 1
    \$\begingroup\$ @Neil Nice find. I thought it was very likely this sequence exists already, I just didn’t know how to find it. \$\endgroup\$
    – Matthew Jensen
    May 2, 2022 at 20:31

17 Answers 17

Reset to default
13
\$\begingroup\$

Python, 31 bytes

f=lambda a:a and(f(a//2)+a%2)/2

Attempt This Online!

Returns the nth term (0-based) as a float.

Python, 54 bytes

a=b=0
while[print(int(bin(a)[:1:-1],2)/-~b)]:a+=1;b|=a

Attempt This Online!

Prints decimal fractions indefinitely.

How?

One can check that if we simply count 0,1,2,3,4 ... and mirror the binary representation at the dot we get 0.0 -> 0.0, 1.0 -> 0.1, 10.0 -> 0.01, 11.0 -> 0.11, 100.0 -> 0.001 ... which happens to be precisely what is needed.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice find! I've updated the challenge rules to use standard sequence output, so you answer can be shorter as a function returning the nth entry: lambda n:int(b:=bin(n)[:1:-1],2)/2**len(b) \$\endgroup\$
    – Matthew Jensen
    May 2, 2022 at 0:32
  • 1
    \$\begingroup\$ @MatthewJensen Thanks! Actually, a recursive function is a bit shorter. \$\endgroup\$
    – loopy walt
    May 2, 2022 at 0:41
6
\$\begingroup\$

JavaScript (ES6), 32 bytes

Returns the \$n\$-th term, 0-indexed.

f=(n,p=0)=>n?f(n>>1,2*p|n&1)/2:p

Try it online!

23 bytes

Using loopy walt's approach, this can be further optimized to:

f=n=>n&&(f(n>>1)+n%2)/2

Try it online!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Charcoal, 8 bytes

Ｉ↨·⁵↨⊗Ｎ²

Try it online! Link is to verbose version of code. Outputs the 0-indexed nth term. Explanation: Another port of @loopywalt's Python answer.

      Ｎ     Input `n`
     ⊗      Doubled
    ↨  ²    Convert to base 2
 ↨·⁵        Interpret as base 0.5
Ｉ           Cast to string
            Implicitly print
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Husk, 4 bytes

½B.ḋ

(or, equivalently, B.ḋD) Try it online!

Outputs n-th term of sequence.

Same approach as Neil's variant of loopy walt's answer.

   ḋ    # convert to binary digits
 B.     # convert from base-0.5
½       # halve

This is much shorter than calculating the numerator (OEIS A030101: mȯḋ↔ḋN) and denominator (OEIS A062383: mö`^2←LḋN) separately & combining (mȯ§/o`^2Lḋ↔ḋN).

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

C (gcc), 63 60 bytes

float d,v;float f(n){for(d=1,v=0;n;n/=2,d*=2)v+=v+n%2;v/=d;}

Try it online!

Saved 3 bytes thanks to Dominic van Essen!!!

Inputs integer \$n\$.
Returns the \$n^\text{th}\$ element in the sequence as a floating point number.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ -3 bytes...? \$\endgroup\$
    – Dominic van Essen
    May 2, 2022 at 12:19
  • \$\begingroup\$ @DominicvanEssen Thanks! :D That wasn't working on my computer - guess I'll have to look into TIO's flag settings. \$\endgroup\$
    – Noodle9
    May 2, 2022 at 13:46
5
\$\begingroup\$

Jelly, 4 bytes

BHḅ.

A monadic Link that accepts a non-negative integer and yields the element of the binary Van der Corput sequence at that 0-indexed index.

Try it online!

How?

Uses the definition given at Wikipedia's entry for a Van der Corput sequence using base two:

$$\text{Corput}_2(n) = \sum_{k=0}^{\text{bitLength}(n)-1}{\text{bit}(n, k)\cdot 2^{-k-1}}$$ $$\text{Corput}_2(n) = \sum_{k=0}^{\text{bitLength}(n)-1}{\frac{1}{2}\text{bit}(n, k)\cdot \frac{1}{2^k}}$$

BHḅ. - Link: non-negative integer, I
B    - binary digits of I
 H   - halve them all
   . - a half
  ḅ  - convert (the list of zeros and halves) from base (one half)
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Factor, 54 42 bytes

[ >bin 48 v-n 0 [ [ 2 / ] bi@ + ] reduce ]

Try it online!

                   ! 9
>bin               ! "1001"
48                 ! "1001" 48
v-n                ! { 1 0 0 1 }                      (convert from binary string to array)
0                  ! { 1 0 0 1 } 0                    (push seed value for reduce)
[ [ 2 / ] bi@ + ]  ! { 1 0 0 1 } 0 [ [ 2 / ] bi@ + ]  (push base 1/2 convert quotation)
reduce             ! 9/16
! =========================================================================================
                   !          (now let's look at each iteration of reduce)
                   ! 0 1      (iteration 1)
[ 2 / ] bi@        ! 0 1/2    (divide both by 2)                      
+                  ! 1/2
                   ! 1/2 0    (iteration 2)
[ 2 / ] bi@        ! 1/4 0
+                  ! 1/4
                   ! 1/4 0    (iteration 3)
[ 2 / ] bi@        ! 1/8 0
+                  ! 1/8
                   ! 1/8 1    (iteration 4 [final])
[ 2 / ] bi@        ! 1/16 1/2
+                  ! 9/16
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 64 bytes

\d+
$*
+`(1+)\1
$+0
01
1
.+
$&/$.&$*01
1
10
+`01
110
0

1+|^
$.&

Try it online! Link is to test suite that generates the results for 0..n (inclusive, 0-indexed). Explanation: Port of @loopywalt's Python answer.

\d+
$*

Convert to unary.

+`(1+)\1
$+0
01
1

Convert to binary.

.+
$&/$.&$*01

Divide by the next power of 2.

1
10
+`01
110
0

Convert to unary, but reading backwards (which is why the power of 2 "ended" in 1).

1+|^
$.&

Convert to decimal, but fix up an input of 0 to output 0.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 38 33 bytes

If[#<1,0,#0@⌊#/2⌋+#~Mod~2]/2&

Try it online!

-5 bytes thanks to att

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 33 bytes \$\endgroup\$
    – att
    May 3, 2022 at 1:33
  • \$\begingroup\$ @att wdym order? \$\endgroup\$
    – naffetS
    May 3, 2022 at 1:35
  • \$\begingroup\$ never mind, I misread it \$\endgroup\$
    – att
    May 3, 2022 at 1:37
3
\$\begingroup\$

PARI/GP, 23 bytes

f(a)=if(a,f(a\2)+a%2)/2

Attempt This Online!

A port of loopy walt's Python answer.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 8 bytes

Double n, get base 2 representation and interpret as base 0.5

0.5/2\2*

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes (-11 from Steffan, -13 from ATT)

#~IntegerReverse~2/2^BitLength@#&

Try it online!

Explanation

#~IntegerReverse~ Take the number reversed

2 in base 2,

/ divided by

2^BitLength@# the nearest greater power of 2 to the input.

If you want to output a list:

Wolfram Language (Mathematica), 48 bytes

Table[i~IntegerReverse~2/2^BitLength@i,{i,0,#}]&

Try it online!

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Reverse@IntegerDigits[#,2]~FromDigits~2 can just be #~IntegerReverse~2 for 46 bytes \$\endgroup\$
    – naffetS
    May 2, 2022 at 18:41
  • \$\begingroup\$ I didn't even know that existed. Thanks! \$\endgroup\$
    – Romanp
    May 2, 2022 at 18:51
  • 2
    \$\begingroup\$ /2^Floor@Log2@#/2 -> /2^BitLength@# \$\endgroup\$
    – att
    May 3, 2022 at 1:27
  • 1
    \$\begingroup\$ BitLength also lets you take off the If, since BitLength@0 is 0. \$\endgroup\$
    – att
    May 3, 2022 at 21:24
2
\$\begingroup\$

Raku, 24 bytes

{:2("0."~.base(2).flip)}

Try it online!

Pity the radix syntax doesn't support non-integer bases.

Explanation

{                      }  # Anonymous code block
         .base(2)          # Convert to base 2
                 .flip     # Reverse
    "0."~                  # Prepend with 0.
 :2(                  )    # Convert back to base 2
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 5 4 bytes

b½.β

Try it Online!

How?

b    # Get the binary digits of the (implicit) input
 ½   # halve them all
   β # Convert from base
  .  # 1/2

-1 byte thanks to emanresu A

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ . = .5 = 1/2. \$\endgroup\$
    – emanresu A
    May 2, 2022 at 19:32
  • \$\begingroup\$ @emanresuA Huh. Why's it not documented... \$\endgroup\$
    – naffetS
    May 2, 2022 at 19:40
  • \$\begingroup\$ Doesn't really need to be. A 0 is assumed before the . if a number starts with ., and a 5 is assumed after. It's probably somewhere in the specs docs \$\endgroup\$
    – emanresu A
    May 2, 2022 at 19:58
1
\$\begingroup\$

ayr, 9 bytes

Pretty boring solution, but it works

.5#.#:&+:

Other solutions include :.5#.#:+:, .5#.-:&#:, and :.5#.-:#:
Try it!

Explained

       #: Convert to base 2
      &   After
    +:    Doubling the input
  #.      Then convert to base 10 from base
.5        1/2
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Desmos, 65 64 bytes

f(n)=total(.5mod(floor(nl),2)l)
l=.5^{[floor(log_2(n+0^n))...0]}

Try it on Desmos!

-1 byte thanks to Aiden Chow

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 16 bytes

Prompts for nth term 0 indexed. Uses the binary/base 0.5 approach.

.5⊥((n⍴2)⊤n←⎕),0

Try it online! Thanks to Dyalog Classic

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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