For Revver and Fevver

This shape reminds me of the feathers on an exotic bird:

feathers

(click or open in new window for full size)


feathers_anim

(animated version)


The shape is created by reversing the digits of a number, so you could say it involves revvers and fevvers. I discovered it when I was looking at the Halton sequence. It’s a sequence of fractions created according to a simple but interesting rule. The rule works like this: take n in base b, reverse it, and divide reverse(n) by the first power of b that is greater thann.

For example, suppose n = 6 and b = 2. In base 2, 6 = 110 and reverse(110) = 011 = 11 = 3. The first power of 2 that is greater than 6 is 2^3 or 8. Therefore, halton(6) in base 2 equals 3/8. Here is the same procedure applied to n = 1..20:

1: halton(1) = 1/10[2] → 1/2
2: halton(10) = 01/100[2] → 1/4
3: halton(11) = 11/100[2] → 3/4
4: halton(100) = 001/1000[2] → 1/8
5: halton(101) = 101/1000[2] → 5/8
6: halton(110) = 011/1000 → 3/8
7: halton(111) = 111/1000 → 7/8
8: halton(1000) = 0001/10000 → 1/16
9: halton(1001) = 1001/10000 → 9/16
10: halton(1010) = 0101/10000 → 5/16
11: halton(1011) = 1101/10000 → 13/16
12: halton(1100) = 0011/10000 → 3/16
13: halton(1101) = 1011/10000 → 11/16
14: halton(1110) = 0111/10000 → 7/16
15: halton(1111) = 1111/10000 → 15/16
16: halton(10000) = 00001/100000 → 1/32
17: halton(10001) = 10001/100000 → 17/32
18: halton(10010) = 01001/100000 → 9/32
19: halton(10011) = 11001/100000 → 25/32
20: halton(10100) = 00101/100000 → 5/32…

Note that the sequence always produces reduced fractions, i.e. fractions in their lowest possible terms. Once 1/2 has appeared, there is no 2/4, 4/8, 8/16…; once 3/4 has appeared, there is no 6/8, 12/16, 24/32…; and so on. If the fractions are represented as points in the interval [0,1], they look like this:

line1_1_2

point = 1/2


line2_1_4

point = 1/4


line3_3_4

point = 3/4


line4_1_8

point = 1/8


line5_5_8

point = 5/8


line6_3_8

point = 3/8


line7_7_8

point = 7/8


line_b2_anim

(animated line for base = 2, n = 1..63)


It’s apparent that Halton points in base 2 will evenly fill the interval [0,1]. Now compare a Halton sequence in base 3:

1: halton(1) = 1/10[3] → 1/3
2: halton(2) = 2/10[3] → 2/3
3: halton(10) = 01/100[3] → 1/9
4: halton(11) = 11/100[3] → 4/9
5: halton(12) = 21/100[3] → 7/9
6: halton(20) = 02/100 → 2/9
7: halton(21) = 12/100 → 5/9
8: halton(22) = 22/100 → 8/9
9: halton(100) = 001/1000 → 1/27
10: halton(101) = 101/1000 → 10/27
11: halton(102) = 201/1000 → 19/27
12: halton(110) = 011/1000 → 4/27
13: halton(111) = 111/1000 → 13/27
14: halton(112) = 211/1000 → 22/27
15: halton(120) = 021/1000 → 7/27
16: halton(121) = 121/1000 → 16/27
17: halton(122) = 221/1000 → 25/27
18: halton(200) = 002/1000 → 2/27
19: halton(201) = 102/1000 → 11/27
20: halton(202) = 202/1000 → 20/27
21: halton(210) = 012/1000 → 5/27
22: halton(211) = 112/1000 → 14/27
23: halton(212) = 212/1000 → 23/27
24: halton(220) = 022/1000 → 8/27
25: halton(221) = 122/1000 → 17/27
26: halton(222) = 222/1000 → 26/27
27: halton(1000) = 0001/10000 → 1/81
28: halton(1001) = 1001/10000 → 28/81
29: halton(1002) = 2001/10000 → 55/81
30: halton(1010) = 0101/10000 → 10/81

And here is an animated gif representing the Halton sequence in base 3 as points in the interval [0,1]:

line_b3_anim


Halton points in base 3 also evenly fill the interval [0,1]. What happens if you apply the Halton sequence to a two-dimensional square rather a one-dimensional line? Suppose the bottom left-hand corner of the square has the co-ordinates (0,0) and the top right-hand corner has the co-ordinates (1,1). Find points (x,y) inside the square, with x supplied by the Halton sequence in base 2 and y supplied by the Halton sequence in base 3. The square will gradually fill like this:

square1

x = 1/2, y = 1/3


square2

x = 1/4, y = 2/3


square3

x = 3/4, y = 1/9


square4

x = 1/8, y = 4/9


square5

x = 5/8, y = 7/9


square6

x = 3/8, y = 2/9


square7

x = 7/8, y = 5/9


square8

x = 1/16, y = 8/9


square9

x = 9/16, y = 1/27…


square_anim

animated square


Read full page: For Revver and Fevver

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s