::  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:

Incoming Gantz-Led Government to Invest in Israel’s Infrastructure

Israel’s incoming prime minister Benny Gantz unveiled an emergency government, to take power following an upcoming confidence vote in the Knesset. The last two MKs required to give Gantz a 61-59 majority, two members of Gantz’s own Blue and White Party wh…

via Pedestrian Observations April 1, 2020

Finding home in the time of coronavirus

Disclaimer: I’m going to say this once. Obviously, I am not happy about the coronavirus’s threat to public health or the economic toll it’s taking. I do not think the existence of this pandemic is good. Just so happens that social distancing and remote wo…

via Holly Elmore March 31, 2020

Massachusetts should shut down immediately

We’ve been running 30x fewer tests than other states, and have been extremely tardy in responding to the Biogen outbreak.

via benkuhn.net March 15, 2020

more     (via openring)

More Posts:


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