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

Fermat Numbers

October 3rd, 2013
math  [html]
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

Recent posts on blogs I like:

Absolute scale corrupts absolutely

The Internet has gotten too big. Growing up, I, like many computery people of my generation, was an idealist. I believed that better, faster communication would be an unmitigated improvement to society. "World peace through better communication,"…

via apenwarr August 19, 2019

Traces

At naptime Anna listens to recordings of novels recorded by Jeff’s grandmother. It is the main way she will know Winnie, as it is the main way I have ever known Winnie. Some of the recordings are missing parts, and Suzie often fills in the first few sente…

via The whole sky August 18, 2019

One Night Ultimate Werewolf

I really like One Night Ultimate Werewolf (ONUW), and recommend trying it out. The Daybreak expansion is also good (but I’d skip the later games in the series). App For those who’ve played a lot and wish the night took 20 seconds rather than a few minutes…

via The sideways view August 18, 2019

more     (via openring)

More Posts:


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