Pages

CodeEval Mersenne prime

CodeEval problem #240 asks to return a comma separated list of all the Marsenne prime numbers smaller than the smallish number (up to 3000) passed as input in a string.

Actually, I found out that the problem description was not crystal clear. A Marsenne prime is a prime number in the form 2**x - 1. However, when I wrote a first python 3 script and I submitted it to CodeEval, I had the surprise to have it partially rejected since I didn't put in the list 2047 when they expected it.

It is easy to see that 2047 is not a prime number, being factorizable in 23 * 89.

Accordingly with the new piece of information, I added an extra test to my test case, now including three tests:
def test_provided_1(self):
    self.assertEqual('3', solution('4'))

def test_provided_2(self):
    self.assertEqual('3, 7, 31, 127', solution('308'))

def test_three_tho(self):
    self.assertEqual('3, 7, 31, 127, 2047', solution('3000'))
I assumed that what they really want to get from us are the "plain" (opposite to prime) Marsenne numbers, in the variation where the index has to be a prime number. In this case, noticing that 2047 is 2**11 - 1, and its Marsenne index is 11, a prime number, also the third test make sense.

Solved this issue, let's see about the code.

Since I didn't want to do the same calculation on and on, I decided to cache some stuff, namely the already calculated Marsenne numbers, as a tuple, index and actual value. And to make my life easier, I have already initialize the cache with the first element in it:
marsennes = [(2, 3)]
The central part of my python script is this following function that ensure the cache contains all the required marsenne numbers for the input. If not, generates the missing ones, then return them.
def get_marsennes(value):
    if value <= marsennes[-1][1]:  # 1
        return trim(value)

    index = marsennes[-1][0]  # 2
    while True:
        index += 1
        if not is_prime(index):  # 3
            continue

        marsenne = 2**index - 1  # 4
        marsennes.append((index, marsenne))

        if marsenne < value:  # 5
            continue
        return marsennes if marsenne == value else marsennes[:-1]
1. If the Marsenne numbers have already been calculated, return them. Minor nuisance, I don't want to return too many of them, so I have written a tiny simple little function, trim(), that returns a trimmed copy of the cache. Not showed here, you can see it on github.
2. Get the index of the biggest Marsenne number in the cache, in the following loop it is increased and stored beside the related Marsenne number.
3. As we find out, we have to ensure the index, used as exponent in the number generation, is a prime. I have written another little function to do this job too.
4. Here is the juice. A new Marsenne number is created and shoveled in the cache.
5. If this Marsenne number is not enough to match the user request, go to the next iteration. Otherwise return the cache, or maybe a copy trimmed of its last element. This loop is one of the rare place where a do-while would have been a nice to have. Alas, Guido van Rossum didn't like it.

Basically, that's it. Ah, OK, we need to convert the list of tuples in a comma separated string, something like:
return ', '.join(map(str, [r[1] for r in result]))
This looks like what the CodeEval guys really wanted from this problem, since I got full marks. So I committed test case and python script to GitHub.

No comments:

Post a Comment