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

    Streaming the Biden Infrastructure Plan

    I streamed my thoughts about the Biden infrastructure plan, and unlike previous streams, I uploaded this to YouTube. I go into more details (and more tangents) on video, but, some key points: Out of the nearly $600 billion in the current proposal that is …

    via Pedestrian Observations April 11, 2021

    Collections: Clothing, How Did They Make it? Part IVb: Cloth Money

    This is the second half of the fourth part of our four part (I, II, III, IVa) look at the production of textiles, particularly wool and linen, in the pre-modern world. Last time, we looked at commercial textile workers and the finishing processes for text…

    via A Collection of Unmitigated Pedantry April 9, 2021

    Notes from “Don’t Shoot the Dog”

    I just finished Karen Pryor’s “Don’t Shoot the Dog: the New Art of Teaching and Training.” Partly because a friend points out that it’s not on Audible and therefore she can’t possibly read it, here are the notes I took and some thoughts. It’s a quick, eas…

    via The whole sky April 2, 2021

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact