### Fermat Numbers

October 3rd, 2013
math  [html]
I noticed while working on something else that `255` is `15*17`, and `65535` is `255*257`. In other words, it sounds like:
```    2^(2^n)-1 * 2^(2^n)+1 = 2^(2^(n+1)) - 1
```
Testing some numbers, it looks like this works:
`n` `2^(2^n)-1` `2^(2^n)+1` `2^(2*(n+1)) - 1`
0 1 3 3
1 3 5 15
2 15 17 255
3 255 257 65535
4 65535 65537 4294967295
And in fact we can prove that it holds for all `n`:
```    2^(2^n)-1 * 2^(2^n)+1
= 2^(2^n)*2^(2^n) + 2^(2^n) - 2^(2^n) - 1
= 2^(2^n)*2^(2^n) - 1
= 2^(2^n + 2^n) - 1
= 2^(2*2^n) - 1
= 2^(2^(n+1)) - 1
```
If `255` is `15*17` and `15` is `3*5`, however, then as long as the numbers `3, 5, 17, 257,` etc. are prime we can build up prime factorizations. So `255` would factor into `3*5*17` and `65535` would factor into `3*5*17*257`. This suggests that if you have a number in the form `2^(2^n)-1` then its prime factorization is the product of `2^(2^i)+1` from `i=0` to `i=n-1`:
`n` `2^(2^n)-1` prime factorization
1 3 3
2 15 3, 5
3 255 3, 5, 17
4 65535 3, 5, 17, 257
5 4294967295 3, 5, 17, 257, 65537
Neat!

But then I thought to try one more, and was very surprised:

`n` `2^(2^n)-1` prime factorization
6 18446744073709551615 3, 5, 17, 257, 641, 65537, 6700417
Why did our nice pattern break? It looks like `2^(2^5)+1` (or `4294967297`) is `641*6700417`. So not all numbers in the form `2^(2^n)+1` are prime, only the first five. The sequence is the Fermat numbers, integer sequence A000215. Such are the dangers of extrapolation.

### Recent posts on blogs I like:

#### Collections: The Queen’s Latin or Who Were the Romans? Part IV: The Color of Purple

This is the fourth part (I, II, III) of our series asking the question “Who were the Romans?” and contrasting the answer we get from the historical evidence with the pop-cultural image of the Romans as a culturally and ethnically homogeneous society typic…

via A Collection of Unmitigated Pedantry July 23, 2021

#### The Leakage Problem

I’ve spent more than ten years talking about the cost of construction of physical infrastructure, starting with subways and then branching on to other things, most. And yet there’s a problem of comparable size when discussing infrastructure waste, which, …

via Pedestrian Observations July 23, 2021

#### Songs about terrible relationships

[Spoilers for several old musicals.] TV Tropes lists dozens of examples of the “I want” song (where the hero of a musical sings about their dream of escaping their small surroundings). After watching a bunch of musicals on maternity leave, I’m wondering h…

via The whole sky July 17, 2021