::  Posts  ::  RSS  ::  ◂◂RSS  ::  Contact

### 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:
n2^(2^n)-1prime factorization
133
2153, 5
32553, 5, 17
4655353, 5, 17, 257
542949672953, 5, 17, 257, 65537
Neat!

But then I thought to try one more, and was very surprised:
n2^(2^n)-1prime factorization
618446744073709551615 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.