project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_97.py (699B)

      1 import sys
      2 import math
      3 from datetime import datetime
      4 
      5 def find_last_x_digits(base, exponent, x):
      6     mod = 10 ** x
      7     exp = 1
      8     squares = []
      9     squares.append(base % mod)
     10     result = 1
     11     
     12     while exp < exponent:
     13         squares.append((squares[-1] ** 2) % mod)
     14         exp = exp * 2
     15     
     16     for i in range(len(squares)):
     17         if (2 ** i) & exponent:
     18             result = (result * squares[i]) % mod
     19         
     20     return result
     21 
     22 base = 2
     23 exponent = 7830457
     24 x = 10
     25 
     26 a = datetime.now()
     27 result = ((find_last_x_digits(base, exponent, x) * 28433) + 1) % (10 ** x)
     28 c = datetime.now() - a
     29 
     30 print result
     31 print "total time: " + str(c.total_seconds())
     32 
     33 print find_last_x_digits(7777777, 7777777, 5)