Tuesday, November 10, 2009

Mersenne Numbers - short sage example

I have used Sagemath and Pari/GP in the past and have found them both very capable Mathematics tools.

Pari/GP has been around a bit longer*, and has many recorded sample code snippets in The On-Line Encyclopaedia of Integer Sequences which AT&T kindly host.

(*Pari/GP has been GPL licensed for free use and modification for the last 15 years or more)

Sage is a bit different than a dedicated number theory program, and could perhaps be described in several ways:
  • A unifying front-end to many computerised algebra and mathematical programs
  • A means of accessing lots of computerised systems using a common language (python)
  • A front-end to Pari/GP (if you are doing Number Theory)
Anyway back to the maths...

See example output from below Sage script on sagemath cloud.

# Most Positive Integers of the form -1+2**n are Composite rather than Prime
#
# There is no significance to the range of numbers 7 through 37
# I selected that range so the primality test is_prime would not
# take too long.
#
# There are more than Mersenne Composites and Mersenne Primes generated by this
# loop. For example 8 gives -1+2**8 = 255 which is not a Mersenne Composite
# nor a Mersenne Prime.
#
# Expect many Falses and just a few Trues (Mersenne Primes) in the output.
#
for n in range(7,37):
mn=-1+2**n
print mn, is_prime(mn)
# True and False are intended to indicate if the number is Prime
# False indicates that the preceding number is a Composite

There is very little involved, and I could have written just the 3 lines and left it uncommented, however a few explanatory comments will hopefully illustrates things a bit better.

What inspired this example was some tabulation I did a while back; an extract is pasted below (click to enlarge):


If you have worked with Mersenne numbers before, then you will have spotted, I hope, that the example loop I used in sage is a bit too simple.

What makes a Mersenne number of any kind, is a prime power of two rather than just any old power of 2. So to be strictly useful, the sage example should only iterate through prime numbers for n, rather than all numbers in the range 7..37.

The great thing about an online version of sage is that anybody can register for an account and submit an example. Please feel free to alter the example I have given here to make it work better as just described, and try sage notebook yourself.
( Easy to take a copy of what I have done and paste it into your own notebook. )

Several universities already host sage online (convenient student access), although it is simple to install on any Ubuntu laptop if you want your own installation rather than relying on the Internet.

Downloads of Sage mathematics for other systems are available here.

Having read this article, and in particular my words on how to improve the example I gave, you might want to come up with your own enhancement to the opening line of Wikipedia's entry (2009 current):
In mathematics, a Mersenne number is a positive integer that is one less than a power of two

Finally a tip for any Pari/GP users who try Sage mathematics:
You may be using is_prime() rather than writing in pari isprime()
and here is quick extract to confirm what you are getting:
sage.rings.arith.is_prime(n, flag=0)
Returns True if prime, and False otherwise. The result is proven correct - this is NOT a pseudo-primality test!.