Fermat Numbers

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