There are 719 errors in this sentence

Here’s a famous paradox (or a variant of it at least):

• There are two errers in this sentence.

The only visible error is the misspelt “errers”. But if the sentence claims to have two errors while having only one, that is another error and there are two errors after all.

Now for another variant. I’m not sure if I’ve thought this up for myself, but try this sentence:

• There are three errors in this sentence.

There are no visible errors in the sentence. Therefore it has one error: the claim that it has three errors when there is in fact no error. But if it has one error, it’s in error to claim that it has three errors. Therefore the sentence has two errors. And if it has two errors, again it’s in error, because it claims to have three errors while having only two. Therefore it has three errors after all.

The same reasoning can be applied to any integral number of errors:

• There are five errors in this sentence.
• There are 719 errors in this sentence.
• There are 1,000,000 errors in this sentence.
• There are 1,000,000,000 errors in this sentence.

No matter how large the number of errors, the sentence becomes true instantly, because each time the sentence makes a false claim, it makes another error. But those “times of error” don’t take place in time, any more than this equation does:

• 2 = 1 + 1/2 + 1/4 + 1/8 + 1/16…

So I think these sentences are instantly true:

• There are infinitely many errors in this sentence.
• There are ∞ errors in this sentence.

But there are infinitely many infinities. Ordinary infinity, the infinity of 1,2,3…, is called ℵ0 or aleph-zero. It’s a countable infinity. Above that comes ℵ1, an uncountable infinity. So does this sentence instantly become true?

• There are ℵ1 errors in this sentence.

I’m not sure. But I think I can argue for the validity of sentences claiming fractional or irrational number of errors:

• There is 1.5 errors in this sentence.
• There are π errors in this sentence.

Let’s have a look at “There is 1.5 errors in this sentence”. There are no visible errors, so there’s one error: the claim that sentence contains 1.5 errors. So now there seems to be another error: the sentence has one error but claims to have 1.5 errors. But does it therefore have two errors? No, because if it has two errors, it’s still in error and has three errors. And that generates another error and another and another, and so on for ever. The sentence becomes unstoppably and infinitely false.

So let’s go back to the point at which the sentence contains one error. Now, the difference between 1 error and 1.5 errors is small — less than a full error. So how big is the error of claiming to have 1.5 errors when having 1 error? Well, it’s obviously 0.5 of an error. So the sentence contains 1.5 errors after all.

Now for “There are π errors in this sentence”. There are no visible errors, so there’s one error: the claim that the sentence contains π errors. Therefore it contains one error. But it claims to have π errors, so it has another error. And if it has 2 errors and claims to have π errors, it has another and third error. But if it has three errors and claims to have π error, it’s still in error. But only slightly — it’s now committing a small amount of an error. How much? It can only be 0.14159265… of an error. Therefore it’s committing 3.14159265… = π errors and is a true sentence.

Now try:

• There is -1 error in this sentence.

What is a negative error? A truth. So I think that sentence is valid too. But I can’t think of how to use i, or the square root of -1, in a sentence like that.

The Power of Powder

• Racine carrée de 2, c’est 1,414 et des poussières… Et quelles poussières ! Des grains de sable qui empêchent d’écrire racine de 2 comme une fraction. Autrement dit, cette racine n’est pas dans Q. — Rationnel mon Q: 65 exercices de styles, Ludmilla Duchêne et Agnès Leblanc (2010)

• The square root of 2 is 1·414 and dust… And what dust! Grains of sand that stop you writing the root of 2 as a fraction. Put another way, this root isn’t in Q [the set of rational numbers].

Gyp Cip

Abundance often overwhelms, but restriction reaps riches. That’s true in mathematics and science, where you can often understand the whole better by looking at only a part of it first — restriction reaps riches. Egyptian fractions are one example in maths. In ancient Egypt, you could have any kind of fraction you liked so long as it was a reciprocal like 1/2, 1/3, 1/4 or 1/5 (well, there were two exceptions: 2/3 and 3/4 were also allowed).

So when mathematicians speak of “Egyptian fractions”, they mean those fractions that can be represented as a sum of reciprocals. Egyptian fractions are restricted and that reaps riches. Here’s one example: how many ways can you add n distinct reciprocals to make 1? When n = 1, there’s one way to do it: 1/1. When n = 2, there’s no way to do it, because 1 – 1/2 = 1/2. Therefore the summed reciprocals aren’t distinct: 1/2 + 1/2 = 1. After that, 1 – 1/3 = 2/3, 1 – 1/4 = 3/4, and so on. By the modern meaning of “Egyptian fraction”, there’s no solution for n = 2.

However, when n = 3, there is a way to do it:

• 1/2 + 1/3 + 1/6 = 1

But that’s the only way. When n = 4, things get better:

• 1/2 + 1/4 + 1/6 + 1/12 = 1
• 1/2 + 1/3 + 1/10 + 1/15 = 1
• 1/2 + 1/3 + 1/9 + 1/18 = 1
• 1/2 + 1/4 + 1/5 + 1/20 = 1
• 1/2 + 1/3 + 1/8 + 1/24 = 1
• 1/2 + 1/3 + 1/7 + 1/42 = 1

What about n = 5, n = 6 and so on? You can find the answer at the Online Encyclopedia of Integer Sequences (OEIS), where sequence A006585 is described as “Egyptian fractions: number of solutions to 1 = 1/x1 + … + 1/xn in positive integers x1 < … < xn”. The sequence is one of the shortest and strangest at the OEIS:

• 1, 0, 1, 6, 72, 2320, 245765, 151182379

When n = 1, there’s one solution: 1/1. When n = 2, there’s no solution, as I showed above. When n = 3, there’s one solution again. When n = 4, there are six solutions. And the OEIS tells you how many solutions there are for n = 5, 6, 7, 8. But n >= 9 remains unknown at the time of writing.

To understand the problem, consider the three reciprocals, 1/2, 1/3 and 1/5. How do you sum them? They have different denominators, 2, 3 and 5, so you have to create a new denominator, 30 = 2 * 3 * 5. Then you have to adjust the numerators (the numbers above the fraction bar) so that the new fractions have the same value as the old:

• 1/2 = 15/30 = (2*3*5 / 2) / 30
• 1/3 = 10/30 = (2*3*5 / 3) / 30
• 1/5 = 06/30 = (2*3*5 / 5) / 30
• 15/30 + 10/30 + 06/30 = (15+10+6) / 30 = 31/30 = 1 + 1/30

Those three reciprocals don’t sum to 1. Now try 1/2, 1/3 and 1/6:

• 1/2 = 18/36 = (2*3*6 / 2) / 36
• 1/3 = 12/36 = (2*3*6 / 3) / 36
• 1/6 = 06/36 = (2*3*6 / 6) / 36
• 18/36 + 12/36 + 06/36 = (18+12+6) / 36 = 36/36 = 1

So when n = 3, the problem consists of finding three reciprocals, 1/a, 1/b and 1/c, such that for a, b, and c:

• a*b*c = a*b + a*c + b*c

There is only one solution: a = 2, b = 3 and c = 6. When n = 4, the problem consists of finding four reciprocals, 1/a, 1/b, 1/c and 1/d, such that for a, b, c and d:

• a*b*c*d = a*b*c + a*b*d + a*c*d + b*c*d

For example:

• 2*4*6*12 = 576
• 2*4*6 + 2*4*12 + 2*6*12 + 4*6*12 = 48 + 96 + 144 + 288 = 576
• 2*4*6*12 = 2*4*6 + 2*4*12 + 2*6*12 + 4*6*12 = 576

Therefore:

• 1/2 + 1/4 + 1/6 + 1/12 = 1

When n = 5, the problem consists of finding five reciprocals, 1/a, 1/b, 1/c, 1/d and 1/e, such that for a, b, c, d and e:

• a*b*c*d*e = a*b*c*d + a*b*c*e + a*b*d*e + a*c*d*e + b*c*d*e

There are 72 solutions and here they are:

• 1/2 + 1/4 + 1/10 + 1/12 + 1/15 = 1 (#1)
• 1/2 + 1/4 + 1/9 + 1/12 + 1/18 = 1 (#2)
• 1/2 + 1/5 + 1/6 + 1/12 + 1/20 = 1 (#3)
• 1/3 + 1/4 + 1/5 + 1/6 + 1/20 = 1 (#4)
• 1/2 + 1/4 + 1/8 + 1/12 + 1/24 = 1 (#5)
• 1/2 + 1/3 + 1/12 + 1/21 + 1/28 = 1 (#6)
• 1/2 + 1/4 + 1/6 + 1/21 + 1/28 = 1 (#7)
• 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 1 (#8)
• 1/2 + 1/3 + 1/12 + 1/20 + 1/30 = 1 (#9)
• 1/2 + 1/4 + 1/6 + 1/20 + 1/30 = 1 (#10)
• 1/2 + 1/5 + 1/6 + 1/10 + 1/30 = 1 (#11)
• 1/2 + 1/3 + 1/11 + 1/22 + 1/33 = 1 (#12)
• 1/2 + 1/3 + 1/14 + 1/15 + 1/35 = 1 (#13)
• 1/2 + 1/3 + 1/12 + 1/18 + 1/36 = 1 (#14)
• 1/2 + 1/4 + 1/6 + 1/18 + 1/36 = 1 (#15)
• 1/2 + 1/3 + 1/10 + 1/24 + 1/40 = 1 (#16)
• 1/2 + 1/4 + 1/8 + 1/10 + 1/40 = 1 (#17)
• 1/2 + 1/4 + 1/7 + 1/12 + 1/42 = 1 (#18)
• 1/2 + 1/3 + 1/9 + 1/30 + 1/45 = 1 (#19)
• 1/2 + 1/4 + 1/5 + 1/36 + 1/45 = 1 (#20)
• 1/2 + 1/5 + 1/6 + 1/9 + 1/45 = 1 (#21)
• 1/2 + 1/3 + 1/12 + 1/16 + 1/48 = 1 (#22)
• 1/2 + 1/4 + 1/6 + 1/16 + 1/48 = 1 (#23)
• 1/2 + 1/3 + 1/9 + 1/27 + 1/54 = 1 (#24)
• 1/2 + 1/3 + 1/8 + 1/42 + 1/56 = 1 (#25)
• 1/2 + 1/3 + 1/8 + 1/40 + 1/60 = 1 (#26)
• 1/2 + 1/3 + 1/10 + 1/20 + 1/60 = 1 (#27)
• 1/2 + 1/3 + 1/12 + 1/15 + 1/60 = 1 (#28)
• 1/2 + 1/4 + 1/5 + 1/30 + 1/60 = 1 (#29)
• 1/2 + 1/4 + 1/6 + 1/15 + 1/60 = 1 (#30)
• 1/2 + 1/4 + 1/5 + 1/28 + 1/70 = 1 (#31)
• 1/2 + 1/3 + 1/8 + 1/36 + 1/72 = 1 (#32)
• 1/2 + 1/3 + 1/9 + 1/24 + 1/72 = 1 (#33)
• 1/2 + 1/4 + 1/8 + 1/9 + 1/72 = 1 (#34)
• 1/2 + 1/3 + 1/12 + 1/14 + 1/84 = 1 (#35)
• 1/2 + 1/4 + 1/6 + 1/14 + 1/84 = 1 (#36)
• 1/2 + 1/3 + 1/8 + 1/33 + 1/88 = 1 (#37)
• 1/2 + 1/3 + 1/10 + 1/18 + 1/90 = 1 (#38)
• 1/2 + 1/3 + 1/7 + 1/78 + 1/91 = 1 (#39)
• 1/2 + 1/3 + 1/8 + 1/32 + 1/96 = 1 (#40)
• 1/2 + 1/3 + 1/9 + 1/22 + 1/99 = 1 (#41)
• 1/2 + 1/4 + 1/5 + 1/25 + 1/100 = 1 (#42)
• 1/2 + 1/3 + 1/7 + 1/70 + 1/105 = 1 (#43)
• 1/2 + 1/3 + 1/11 + 1/15 + 1/110 = 1 (#44)
• 1/2 + 1/3 + 1/8 + 1/30 + 1/120 = 1 (#45)
• 1/2 + 1/4 + 1/5 + 1/24 + 1/120 = 1 (#46)
• 1/2 + 1/5 + 1/6 + 1/8 + 1/120 = 1 (#47)
• 1/2 + 1/3 + 1/7 + 1/63 + 1/126 = 1 (#48)
• 1/2 + 1/3 + 1/9 + 1/21 + 1/126 = 1 (#49)
• 1/2 + 1/3 + 1/7 + 1/60 + 1/140 = 1 (#50)
• 1/2 + 1/4 + 1/7 + 1/10 + 1/140 = 1 (#51)
• 1/2 + 1/3 + 1/12 + 1/13 + 1/156 = 1 (#52)
• 1/2 + 1/4 + 1/6 + 1/13 + 1/156 = 1 (#53)
• 1/2 + 1/3 + 1/7 + 1/56 + 1/168 = 1 (#54)
• 1/2 + 1/3 + 1/8 + 1/28 + 1/168 = 1 (#55)
• 1/2 + 1/3 + 1/9 + 1/20 + 1/180 = 1 (#56)
• 1/2 + 1/3 + 1/7 + 1/54 + 1/189 = 1 (#57)
• 1/2 + 1/3 + 1/8 + 1/27 + 1/216 = 1 (#58)
• 1/2 + 1/4 + 1/5 + 1/22 + 1/220 = 1 (#59)
• 1/2 + 1/3 + 1/11 + 1/14 + 1/231 = 1 (#60)
• 1/2 + 1/3 + 1/7 + 1/51 + 1/238 = 1 (#61)
• 1/2 + 1/3 + 1/10 + 1/16 + 1/240 = 1 (#62)
• 1/2 + 1/3 + 1/7 + 1/49 + 1/294 = 1 (#63)
• 1/2 + 1/3 + 1/8 + 1/26 + 1/312 = 1 (#64)
• 1/2 + 1/3 + 1/7 + 1/48 + 1/336 = 1 (#65)
• 1/2 + 1/3 + 1/9 + 1/19 + 1/342 = 1 (#66)
• 1/2 + 1/4 + 1/5 + 1/21 + 1/420 = 1 (#67)
• 1/2 + 1/3 + 1/7 + 1/46 + 1/483 = 1 (#68)
• 1/2 + 1/3 + 1/8 + 1/25 + 1/600 = 1 (#69)
• 1/2 + 1/3 + 1/7 + 1/45 + 1/630 = 1 (#70)
• 1/2 + 1/3 + 1/7 + 1/44 + 1/924 = 1 (#71)
• 1/2 + 1/3 + 1/7 + 1/43 + 1/1806 = 1 (#72)

All the sums start with 1/2 except for one:

• 1/2 + 1/5 + 1/6 + 1/12 + 1/20 = 1 (#3)
• 1/3 + 1/4 + 1/5 + 1/6 + 1/20 = 1 (#4)

Here are the solutions in another format:

(2,4,10,12,15), (2,4,9,12,18), (2,5,6,12,20), (3,4,5,6,20), (2,4,8,12,24), (2,3,12,21,28), (2,4,6,21,28), (2,4,7,14,28), (2,3,12,20,30), (2,4,6,20,30), (2,5,6,10,30), (2,3,11,22,33), (2,3,14,15,35), (2,3,12,18,36), (2,4,6,18,36), (2,3,10,24,40), (2,4,8,10,40), (2,4,7,12,42), (2,3,9,30,45), (2,4,5,36,45), (2,5,6,9,45), (2,3,12,16,48), (2,4,6,16,48), (2,3,9,27,54), (2,3,8,42,56), (2,3,8,40,60), (2,3,10,20,60), (2,3,12,15,60), (2,4,5,30,60), (2,4,6,15,60), (2,4,5,28,70), (2,3,8,36,72), (2,3,9,24,72), (2,4,8,9,72), (2,3,12,14,84), (2,4,6,14,84), (2,3,8,33,88), (2,3,10,18,90), (2,3,7,78,91), (2,3,8,32,96), (2,3,9,22,99), (2,4,5,25,100), (2,3,7,70,105), (2,3,11,15,110), (2,3,8,30,120), (2,4,5,24,120), (2,5,6,8,120), (2,3,7,63,126), (2,3,9,21,126), (2,3,7,60,140), (2,4,7,10,140), (2,3,12,13,156), (2,4,6,13,156), (2,3,7,56,168), (2,3,8,28,168), (2,3,9,20,180), (2,3,7,54,189), (2,3,8,27,216), (2,4,5,22,220), (2,3,11,14,231), (2,3,7,51,238), (2,3,10,16,240), (2,3,7,49,294), (2,3,8,26,312), (2,3,7,48,336), (2,3,9,19,342), (2,4,5,21,420), (2,3,7,46,483), (2,3,8,25,600), (2,3,7,45,630), (2,3,7,44,924), (2,3,7,43,1806)


Note

Strictly speaking, there are two solutions for n = 2 in genuine Egyptian fractions, because 1/3 + 2/3 = 1 and 1/4 + 3/4 = 1. As noted above, 2/3 and 3/4 were permitted as fractions in ancient Egypt.

Fract-Hills

The Farey sequence is a fascinating sequence of fractions that divides the interval between 0/1 and 1/1 into smaller and smaller parts. To find the Farey fraction a[i] / b[i], you simply find the mediant of the Farey fractions on either side:

• a[i] / b[i] = (a[i-1] + a[i+1]) / (b[i-1] + b[i+1])

Then, if necessary, you reduce the numerator and denominator to their simplest possible terms. So the sequence starts like this:

• 0/1, 1/1

To create the next stage, find the mediant of the two fractions above: (0+1) / (1+1) = 1/2

• 0/1, 1/2, 1/1

For the next stage, there are two mediants to find: (0+1) / (1+2) = 1/3, (1+1) / (2+3) = 2/3

• 0/1, 1/3, 1/2, 2/3, 1/1

Note that 1/2 is the mediant of 1/3 and 2/3, that is, 1/2 = (1+2) / (3+3) = 3/6 = 1/2. The next stage is this:

• 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1

Now 1/2 is the mediant of 2/5 and 3/5, that is, 1/2 = (2+3) / (5+5) = 5/10 = 1/2. Further stages go like this:

• 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 1/1

• 0/1, 1/6, 1/5, 2/9, 1/4, 3/11, 2/7, 3/10, 1/3, 4/11, 3/8, 5/13, 2/5, 5/12, 3/7, 4/9, 1/2, 5/9, 4/7, 7/12, 3/5, 8/13, 5/8, 7/11, 2/3, 7/10, 5/7, 8/11, 3/4, 7/9, 4/5, 5/6, 1/1

• 0/1, 1/7, 1/6, 2/11, 1/5, 3/14, 2/9, 3/13, 1/4, 4/15, 3/11, 5/18, 2/7, 5/17, 3/10, 4/13, 1/3, 5/14, 4/11, 7/19, 3/8, 8/21, 5/13, 7/18, 2/5, 7/17, 5/12, 8/19, 3/7, 7/16, 4/9, 5/11, 1/2, 6/11, 5/9, 9/16, 4/7, 11/19, 7/12, 10/17, 3/5, 11/18, 8/13, 13/21, 5/8, 12/19, 7/11, 9/14, 2/3, 9/13, 7/10, 12/17, 5/7, 13/18, 8/11, 11/15, 3/4, 10/13, 7/9, 11/14, 4/5, 9/11, 5/6, 6/7, 1/1

The Farey sequence is actually a fractal, as you can see more easily when it’s represented as an image:

Farey fractal stage #1, representing 0/1, 1/2, 1/1

Farey fractal stage #2, representing 0/1, 1/3, 1/2, 2/3, 1/1

Farey fractal stage #3, representing 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1

Farey fractal stage #4, representing 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 1/1

Farey fractal stage #5

Farey fractal stage #6

Farey fractal stage #7

Farey fractal stage #8

Farey fractal stage #9

Farey fractal stage #10

Farey fractal (animated)

That looks like the slope of a hill to me, so you could call it a Farey fract-hill. But Farey fract-hills or Farey fractals aren’t confined to the unit interval, 0/1 to 1/1. Here are Farey fractals for the intervals 0/1 to n/1, n = 1..10:

Farey fractal for interval 0/1 to 1/1

Farey fractal for interval 0/1 to 2/1, beginning 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1, 5/4, 4/3, 7/5, 3/2, 8/5, 5/3, 7/4, 2/1

Farey fractal for interval 0/1 to 3/1, beginning 0/1, 1/3, 1/2, 2/3, 1/1, 5/4, 4/3, 7/5, 3/2, 8/5, 5/3, 7/4, 2/1, 7/3, 5/2, 8/3, 3/1

Farey fractal for interval 0/1 to 4/1, beginning
0/1, 1/3, 1/2, 2/3, 1/1, 4/3, 3/2, 5/3, 2/1, 7/3, 5/2, 8/3, 3/1, 10/3, 7/2, 11/3, 4/1

Farey fractal for interval 0/1 to 5/1, beginning 0/1, 1/1, 5/4, 10/7, 5/3, 7/4, 2/1, 7/3, 5/2, 8/3, 3/1, 13/4, 10/3, 25/7, 15/4, 4/1, 5/1

Farey fractal for interval 0/1 to 6/1, beginning 0/1, 1/2, 1/1, 4/3, 3/2, 5/3, 2/1, 5/2, 3/1, 7/2, 4/1, 13/3, 9/2, 14/3, 5/1, 11/2, 6/1

Farey fractal for interval 0/1 to 7/1, beginning 0/1, 7/5, 7/4, 2/1, 7/3, 21/8, 14/5, 3/1, 7/2, 4/1, 21/5, 35/8, 14/3, 5/1, 21/4, 28/5, 7/1

Farey fractal for interval 0/1 to 8/1, beginning 0/1, 1/2, 1/1, 3/2, 2/1, 5/2, 3/1, 7/2, 4/1, 9/2, 5/1, 11/2, 6/1, 13/2, 7/1, 15/2, 8/1

Farey fractal for interval 0/1 to 9/1, beginning 0/1, 1/1, 3/2, 2/1, 3/1, 7/2, 4/1, 13/3, 9/2, 14/3, 5/1, 11/2, 6/1, 7/1, 15/2, 8/1, 9/1

Farey fractal for interval 0/1 to 10/1, beginning 0/1, 5/4, 5/3, 2/1, 5/2, 3/1, 10/3, 15/4, 5/1, 25/4, 20/3, 7/1, 15/2, 8/1, 25/3, 35/4, 10/1

The shape of the slope is determined by the factorization of n:

n = 12 = 2^2 * 3

n = 16 = 2^4

n = 18 = 2 * 3^2

n = 20 = 2^2 * 5

n = 25 = 5^2

n = 27 = 3^3

n = 32 = 2^5

n = 33 = 3 * 11

n = 42 = 2 * 3 * 7

n = 64 = 2^6

n = 65 = 5 * 13

n = 70 = 2 * 5 * 7

n = 77 = 7 * 11

n = 81 = 3^4

n = 96 = 2^5 * 3

n = 99 = 3^2 * 11

n = 100 = 2^2 * 5^2

Farey fractal-hills, n = various

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