### 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:

#### Willingness to look stupid

People frequently1 think that I'm very stupid. I don't find this surprising, since I don't mind if other people think I'm stupid, which means that I don't adjust my behavior to avoid seeming stupid, which results in people thinking tha…

via Posts on Dan Luu October 21, 2021

#### Experiences in raising children in shared housing

Sometimes I see posts about people’s hope to raise children in a group housing situation, and it often seems overly optimistic to me. In particular they seem to expect that there will be more shared childcare than I think should be expected. Today I talke…

via The whole sky October 18, 2021

#### EDT with updating double counts

I recently got confused thinking about the following case: Calculator bet: I am offered the opportunity to bet on a mathematical statement X to which I initially assign 50% probability (perhaps X = 139926 is a quadratic residue modulo 314159). I have acce…

via The sideways view October 12, 2021