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

    Yet another world spirit sock puppet

    Crossposted from world spirit sock puppet. I have almost successfully made and made decent this here my new blog, in spite of little pre-existing familiarity with relevant tools beyond things like persistence in the face of adversity and Googling things. …

    via Meteuphoric October 25, 2020

    Things You Might Have Missed, October 21, 2020

    Hey folks! I am, as I mentioned last week, taking this week off in an effort to catch up on my sanity and also some grading and writing I need to be doing. But I didn’t want to leave you with nothing, so I thought I might use this as an opportunity to dir…

    via A Collection of Unmitigated Pedantry October 23, 2020

    Job Sprawl as Deurbanization

    A few years ago, Aaron Renn was writing, I think about the General Electric headquarters’ move from suburban New York to Downtown Boston in 2016, that in the future, city center jobs would go to high-value industries like corporate HQs and professional se…

    via Pedestrian Observations October 23, 2020

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact