Tuesday, November 9, 2010

Euler Problem 97: Find last 10 digits of a big prime number

First, I'm glad that I've managed to solve 39 problems by now. Since the last problem, I don't find really interesting example to blog, but this problem 97 deserves a blog. Not really because Scala is good in answering this, but because the problem itself is interesting.

The problem is expressed in a little bit history of prime number, but finally the real problem is here: "What is the 10 last digits of the following prime number: 28433×27830457+ 1. Looks intimidating, right ? Try give a try calculating 28433 * (2: BigInt).pow(7830457) won't work, simply because its too large. Another thing is needed.

The other thing is the modular exponentiation, excellently explained here: http://en.wikipedia.org/wiki/Modular_exponentiation . Basically, the techniques are very useful to compute bmod m by observing that (a*b) mod m = ( (a mod m)  * (b mod m) ) mod m. 

Taking that into account,   bmod m can be calculated as ( (b mod m) * (b mod m) )  mod m, and 
bmod m =( ( b mod m) * ( bmod m) )mod m and so on. 

When this is translated to Scala it becomes:

 1 dev div(b: Long, exp: Long, m: BigInt): BigInt = {
 2   def div(b: Long, counter: Long, 
 3         m: BigInt, result: BigInt): BigInt = {
 4    if (counter == 0) 
 5       result
 7     else div(b, counter - 1, m, (result * b) % m)
 8   }
 9   div(b, exp, m, 1)
10 }

With this in our hand, we can then get the last 10 digit of 27830457 which nothing less than  27830457
mod 10000000000. Using div method above, we can get then the last 10 digits of the term. We can multiply the result with 28433 and then add 1 to get the answer to the problem.
OK. That was my 39th solved problem.

No comments: