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.

Comment via: google plus, facebook, substack

Recent posts on blogs I like:

Paid Subscriber Questions Post

I have picked up a lot of new paid subscribers since the last time I did something like this, so: let's do a subscriber questions post!

via Thing of Things July 21, 2025

Retrospective on life tracking and effectiveness systems

I’ve been doing life tracking for around 10 years, and this post is looking back at some things I learned from the data (since my previous retrospective in 2017). Highlights include what I get out of the Oura ring, correlations between sleep and deep work…

via Victoria Krakovna July 4, 2025

Elixir's Last Dance

On May 18th, the contra dance band Elixir had their last gig ever. The dance was packed: there were three hundred people. It was the only dance BIDA has ever done where they sold tickets. People flew from across the country just to hear Elixir play one la…

via Lily Wise's Blog Posts June 5, 2025

more     (via openring)