# Problem #97

Now this prob­lem was inter­est­ing! It asked for us to find the last 10 dig­its of a very large Mersenne Prime dis­cov­ered in 2004 of the form 28433×27830457+1.

I solved this prob­lem three dif­fer­ent ways. The first was by my own logic, the other two, due to some research. My thought was that cal­cu­lat­ing 2n can be done in a loop that mul­ti­plies the pre­vi­ous value by 2 on each iter­a­tion. Rais­ing it to the 7,830,457th power though would not only take for­ever, but could be hard to store in mem­ory. So I fig­ured that we really only care about the last 10 dig­its. This meant I could mul­ti­ple the pre­vi­ous value by 2 on each iter­a­tion, but store for the next iter­a­tion a con­sist­ing of only the last ten dig­its. Python’s list syn­tax of [-10:] came in mighty handy for this.

My Method
==============
Result: 8739992577
Time: 9.89434504509

def my_method():
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 sec­onds, but not as fast as it could be.

The next method I tried was to uti­lize the bit­wise shift oper­a­tor. I saw this for a C++ solu­tion in the forums after solv­ing it and won­dered if Python had a bit­wise shift. Turns out it does. Hav­ing a base of 2 for the pow­ers is what makes this pos­si­ble. Rather than mul­ti­ply­ing a num­ber by 2, we can shift it’s binary value to the left by one posi­tion for the same affect. CPU’s are typ­i­cally faster at bit shift­ing than they are at mul­ti­ply­ing. This solu­tion took less than 2 sec­onds! That’s quite an improvement.

Bit­wise Method
==============
Result: 8739992577
Time: 1.6119530201

def bit­wise():
print ““
print “Bit­wise 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 read­ing this arti­cle on OSIX about quickly cal­cu­lat­ing inte­ger pow­ers. It pro­posed a func­tion in C# that used recur­sion to cal­cu­late a power in O(logn) time rather than the O(n) time that the first two meth­ods imple­mented. I trans­lated the code to Python, and sure enough, it solves this prob­lem in less than half of a second!

Power Method
==============
Result: 8739992577
Time: 0.471854925156

def get_power(a,n): # a^n
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)

## One thought on “Problem #97”

1. Pingback: Problem #53 « rarmknecht