project-euler

commit b37fcb5bc604d8e53987e2e71a634d0e454c84a4
parent ba355c20a8984bdd84422c032fcca3d52020f47a
Author: Michael Percival <Michael Percival>
Date:   Mon, 21 Aug 2017 15:55:16 +0100

Euler 97 complete

Diffstat:
A
Euler_97.py
 | 
34
++++++++++++++++++++++++++++++++++

1 file changed, 34 insertions(+), 0 deletions(-)
diff --git a/Euler_97.py b/Euler_97.py
@@ -0,0 +1,33 @@
+import sys
+import math
+from datetime import datetime
+
+def find_last_x_digits(base, exponent, x):
+	mod = 10 ** x
+	exp = 1
+	squares = []
+	squares.append(base % mod)
+	result = 1
+	
+	while exp < exponent:
+		squares.append((squares[-1] ** 2) % mod)
+		exp = exp * 2
+	
+	for i in range(len(squares)):
+		if (2 ** i) & exponent:
+			result = (result * squares[i]) % mod
+		
+	return result
+
+base = 2
+exponent = 7830457
+x = 10
+
+a = datetime.now()
+result = ((find_last_x_digits(base, exponent, x) * 28433) + 1) % (10 ** x)
+c = datetime.now() - a
+
+print result
+print "total time: " + str(c.total_seconds())
+
+print find_last_x_digits(7777777, 7777777, 5)+
\ No newline at end of file