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

    How to extend pockets

    Make women's pants pockets big enough to hold a phone properly The post How to extend pockets appeared first on Otherwise.

    via Otherwise May 19, 2022

    Buckingham Palace

    I love England. Especially because of the big castle called Buckingham Palace. I got to see the outside there, but my mom showed me some pictures of the inside. I love it there. But the outside doesn't look very fancy to me. But I never knew why those …

    via Anna Wise's Blog Posts April 25, 2022

    What is causality to an evidential decision theorist?

    (Subsumed by: Timeless Decision Theory, EDT=CDT) People sometimes object to evidential decision theory by saying: “It seems like the distinction between correlation and causation is really important to making good decisions in practice. So how can a theor…

    via The sideways view April 17, 2022

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact