Now this problem was interesting! It asked for us to find the last 10 digits of a very large Mersenne Prime discovered in 2004 of the form 28433×2^{7830457}+1.

I solved this problem three different ways. The first was by my own logic, the other two, due to some research. My thought was that calculating 2^{n} can be done in a loop that multiplies the previous value by 2 on each iteration. Raising it to the 7,830,457^{th} power though would not only take forever, but could be hard to store in memory. So I figured that we really only care about the last 10 digits. This meant I could multiple the previous value by 2 on each iteration, but store for the next iteration a consisting of only the last ten digits. Python’s list syntax of [-10:] came in mighty handy for this.

My Method

==============

Result: 8739992577

Time: 9.89434504509

print ““

print “My Method“

print “==============“

last=“2”

start = time.time()

for p in range(2,7830458):

last = str(int(last)*2)

last = last[-10:]

result = str(28433*int(last)+1)

stop = time.time()

print “Result: “+result[-10:]

print “Time: “+str(stop-start)

It was fairly quick, sub 10 seconds, but not as fast as it could be.

The next method I tried was to utilize the bitwise shift operator. I saw this for a C++ solution in the forums after solving it and wondered if Python had a bitwise shift. Turns out it does. Having a base of 2 for the powers is what makes this possible. Rather than multiplying a number by 2, we can shift it’s binary value to the left by one position for the same affect. CPU’s are typically faster at bit shifting than they are at multiplying. This solution took less than 2 seconds! That’s quite an improvement.

Bitwise Method

==============

Result: 8739992577

Time: 1.6119530201

print ““

print “Bitwise Method“

print “==============“

start = time.time()

ans = 1

for n in range(1,7830458):

ans = ans « 1

ans = ans % 10000000000

ans = ans * 28433

ans = ans % 10000000000

ans = ans + 1

stop = time.time()

print “Result: “+str(ans)

print “Time: “+str(stop-start)

I’m not sure how, but I ended up reading this article on OSIX about quickly calculating integer powers. It proposed a function in C# that used recursion to calculate a power in O(logn) time rather than the O(n) time that the first two methods implemented. I translated the code to Python, and sure enough, it solves this problem in less than half of a second!

Power Method

==============

Result: 8739992577

Time: 0.471854925156

if n==0:

return 1

if a==0:

return 0

if n%2==0:

return get_power(a*a, n/2)

else:

return a*get_power(a*a, n/2)

return 0

def power():

print ““

print “Power Method“

print “==============“

start = time.time()

value = get_power(2,7830457)

ans = 28433*value+1

ans = ans % 10000000000

stop = time.time()

print “Result: “+str(ans)

print “Time: “+str(stop-start)

Pingback: Problem #53 « rarmknecht