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
\$\endgroup\$
9
  • 2
    \$\begingroup\$ It must follow this order, otherwise the challenge becomes too trivial! \$\endgroup\$ May 1 at 22:06
  • 2
    \$\begingroup\$ The numerator is A030101. \$\endgroup\$
    – Arnauld
    May 2 at 0:00
  • 3
    \$\begingroup\$ @Arnauld Nice, the denominator is A062383 \$\endgroup\$ May 2 at 0:16
  • 2
    \$\begingroup\$ Apparently this is also known as the binary van der Corput sequence. \$\endgroup\$
    – Neil
    May 2 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\$ May 2 at 20:31

17 Answers 17

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.

\$\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\$ May 2 at 0:32
  • 1
    \$\begingroup\$ @MatthewJensen Thanks! Actually, a recursive function is a bit shorter. \$\endgroup\$
    – loopy walt
    May 2 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!

\$\endgroup\$
5
\$\begingroup\$

Charcoal, 8 bytes

I↨·⁵↨⊗N²

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

      N     Input `n`
     ⊗      Doubled
    ↨  ²    Convert to base 2
 ↨·⁵        Interpret as base 0.5
I           Cast to string
            Implicitly print
\$\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).

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

\$\endgroup\$
2
  • \$\begingroup\$ -3 bytes...? \$\endgroup\$ May 2 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 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)
\$\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
\$\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.

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

\$\endgroup\$
3
  • \$\begingroup\$ 33 bytes \$\endgroup\$
    – att
    May 3 at 1:33
  • \$\begingroup\$ @att wdym order? \$\endgroup\$
    – Steffan
    May 3 at 1:35
  • \$\begingroup\$ never mind, I misread it \$\endgroup\$
    – att
    May 3 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.

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

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

\$\endgroup\$
3
  • \$\begingroup\$ . = .5 = 1/2. \$\endgroup\$
    – emanresu A
    May 2 at 19:32
  • \$\begingroup\$ @emanresuA Huh. Why's it not documented... \$\endgroup\$
    – Steffan
    May 2 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 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
\$\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

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

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

\$\endgroup\$

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.