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

#### Transfers from Infrequent to Frequent Vehicles

Imagine yourself taking a train somewhere, and imagine the train is big and infrequent. Let’s say it’s the commuter train from New York down the Northeast Corridor to Newark Airport, or perhaps a low-cost OuiGo TGV from Lyon to Paris. Now imagine that you…

via Pedestrian Observations January 20, 2020

#### Veganism and restrictive eating

I’m reading the book Intuitive Eating, which I highly recommend. I was looking for something like it that could get me back to trusting my biological hunger without worrying that I need to control myself or my weight. It’s raised my consciousness to the w…

via Holly Elmore January 17, 2020

#### Algorithms interviews: theory vs. practice

When I ask people at trendy big tech companies why algorithms quizzes are mandatory, the most common answer I get is something like "we have so much scale, we can't afford to have someone accidentally write an O(n^2) algorithm and bring the site d…

via Posts on Dan Luu January 5, 2020