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

    Collections: Bread, How Did they Make it? Part III: Actually Farming

    As the third part (I, II) of our look at the basic structure of food production in the pre-modern world (particularly farming grain to make bread) we’re going to finally look at how one actually farms grain to make bread. Now that we have all of our farme…

    via A Collection of Unmitigated Pedantry August 7, 2020

    The Limits of Regional Rail

    I recently found myself involved in a discussion about Boston regional rail that involved a proposal to do more thorough regional rail-subway integration. Normally, S-Bahn systems mix some aspects of longer-range regional rail and some aspects of urban me…

    via Pedestrian Observations August 5, 2020

    Tools for keeping focused

    no badges • close slack • check email 1x/day • keep todos visible • use rss • kindle + rss • hide phone apps • block ui elements • block sites • better window switcher • no tabs

    via benkuhn.net August 4, 2020

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact