### Fermat Numbers

October 3rd, 2013
math
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:

#### How did we decide to have a kid?

...and then some more kids? The post How did we decide to have a kid? appeared first on Otherwise.

via Otherwise January 28, 2023

#### My Rainbow Kit

For Christmas I got a really fun kit about rainbows. It had a rainbow catcher, a really cool necklace, a streamer thingy, and it also had a really really cool pinwheel, and it also had a bracelet and a pinata. Unfortunately the pinata didn't work out …

via Anna Wise's Blog Posts January 5, 2023

#### Phones

I think that once a kid is in third grade they should be able to get a phone. I think that while sometimes parents might want kids not to have them at certain ages, phones can be quite useful at times. Tablets don't have GPS, they don't have WiFi…

via Lily Wise's Blog Posts January 5, 2023