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