Binary surprise

As mentioned in the previous post, the Gauss-Wantzel theorem says you can construct a regular n-gon with a straight edge and compass if and only if n has the form 2^kF where k is a non-negative integer and F is a product of distinct Fermat primes. Let's look at the binary representation of these values of n.

The 2^k factor means that when written in binary, n ends in k zeros.

The only known Fermat primes are 3, 5, 17, 257, and 65537. This means that as far as we know, there are only 2⁵ = 32 possible values for F: each of the five known Fermat primes is either a factor of F or not [1].

Here are the binary values of the possible values of F.

111 101 1111 10001 110011 1010101 11111111 100000001 1100000011 10100000101 111100001111 1000100010001 11001100110011 101010101010101 1111111111111111 10000000000000001 110000000000000011 1010000000000000101 11110000000000001111 100010000000000010001 1100110000000000110011 10101010000000001010101 111111110000000011111111 1000000010000000100000001 11000000110000001100000011 101000001010000010100000101 1111000011110000111100001111 10001000100010001000100010001 110011001100110011001100110011 1010101010101010101010101010101 11111111111111111111111111111111

If you squint, you can see a pattern that looks sorta like a Sierpinski triangle. To make it easier to see, here's a image of the numbers with the 1's replaced with black blocks and the 0's replaced with white space.

It's not just like a Sierpinski triangle, it is a Sierpinski triangle!

Python code

Here's Python code to print the binary numbers above.

from itertools import chain, combinationsfrom functools import reducedef product(lst): return reduce(lambda x,y: x*y, lst, 1)def powerset(iterable): xs = list(iterable) return chain.from_iterable( combinations(xs,n) for n in range(len(xs)+1) )N = 5# The first N Fermat numbersF = [2**(2**i)+1 for i in range(N)]s = {product(x) for x in powerset(F)}for f in sorted(s): print(format(f, 'b'))

You can continue the pattern by taking all products of subsets of the first few Fermat numbers, but only the first five Fermat numbers are Fermat primes [2]. If you set N to 6 in the code above, for example, you'll get a triangle with 64 rows.

More on Sierpinskyi

At first the Sierpinksi triangle seems a fun but someone arbitrary exercise: what happens if I take the middle triangle out of a larger triangle and keep doing that recursively on what's left? But then it comes up in unexpected ways. I certainly didn't expect it when I printed out the binary numbers above.

Here are a couple other blog posts where there Sierpinski triangle pops up: one on cellular automata and one on the chaos game.

***

[1] We allow the possibility that we could have an empty product of Fermat primes, which we interpret at 1. You could think of it this way: each Fermat prime either has an exponent of 0 or 1, and we allow the possibility that all exponents are 0.

[2] As far as we know. The next several Fermat numbers are definitely not prime, but nobody has proved that there isn't another Fermat number past 65537 that's prime.