For 2ⁿ – 1 to be prime we also need n itself to be prime, but that is not sufficient. For example, 2¹¹ – 1 is composite even though 11 is prime. However, if you look at tables of Mersenne primes it is interesting to note that if you start with 2 and use that to make a new number 2ⁿ – 1 with n = 2 you get 3, then recycling the 3 you get 7, use n = 7 and you get 127, another prime! How long could this go on?
Let f(n) = 2ⁿ – 1. The iterations you get, starting from 2, are f⁰(2) = 2, f¹(2) = 3, f²(2) = 7, f³(2) = 127, f⁴(2) = 1701411834604692317316873037158884105727.
It turns out these are all prime! But what of the next one??? Well, it may be a very long time before any of us know. The largest value of n for which 2ⁿ – 1 is known to be prime is n = 57885161, and that after a concerted effort using volunteers from around the globe. Not much chance of answering this one in our lifetimes, unless some really new idea arrives.Before you make a hasty conjecture (as has already been done), a cautionary piece of history is in order. If you define a new function to iterate you get some other interesting numbers. Let g(n) = n² – 2n + 2. Then the iterates are g⁰(3) = 3, g¹(3) = 5, g²(3) = 17, g³(3) = 257, g⁴(3) = 65537, and all of these are prime! So, with forgivable excitement, the conjecture was made that all of these will be prime, especially as the next one, g⁵(2) = 4294967297, was much too large at the time for mere mortals to conceive of factoring with their bare hands.
None, that is, until Euler combined his genius with an impish disbelief in Fermat’s conjecture to discover that g⁵(2) = 4294967297 = 641 * 6700417. And since then we have found many more composite Fermat numbers, and no further Fermat primes, leading to the complementary conjecture that all the rest are composite! It seems that we never learn to be humble around these things…
It takes a larger number to be “forever beyond reach” these days. Rather than the now puny 4294967297 we cower before f⁵(2) = 2¹⁷⁰¹⁴¹¹⁸³⁴⁶⁰⁴⁶⁹²³¹⁷³¹⁶⁸⁷³⁰³⁷¹⁵⁸⁸⁸⁴⁴¹⁰⁵⁷²⁷ – 1, and who can blame us?
Like this:
Like Loading...
Read Full Post »
Addition is the most elementary arithmetic operation required of computers. Their invention and development has almost entirely been to do arithmetic extremely fast. I will present the simplest binary adder circuits (ripple carry adder), show some surprising results about carry propagation, develop carry look-ahead circuits for log-time addition, and then talk about redundant number systems and constant time addition and, consequently, log-time multiplication.
