Skip to content

Instantly share code, notes, and snippets.

@RaphaelAslanian
Created January 14, 2018 11:00
Show Gist options
  • Save RaphaelAslanian/7fc2b87084eabf008c53b44a778f9ed7 to your computer and use it in GitHub Desktop.
Save RaphaelAslanian/7fc2b87084eabf008c53b44a778f9ed7 to your computer and use it in GitHub Desktop.
Last two digits of x^n
def last_digits_power(n):
"""Display the last two digits of n to the power of n"""
result = last_digits(n, n)
result_tens, result_units = result // 10, result % 10
print("First digit: {}, Second digit: {}".format(result_tens, result_units))
return result_tens, result_units
def last_digits(base, exponent):
"""
Computes the modulo 100 of <base> to the power of <exponent>.
Computation method documentation found here:
http://learningroots.in/cat-and-omet/quant/last-two-digits-cyclicity/
https://www.justquant.com/numbertheory/last-two-digits-of-large-number/
"""
if not (isinstance(base, int) and isinstance(exponent, int)):
raise TypeError("Base and exponent should be of type int, received: {} and {}.".format(type(base), type(exponent)))
if base < 0 or exponent < 0:
raise ValueError("Base and exponent should be positive")
# All hundreds', thousands' digits and higher are irrelevant to compute the last two digits.
base = base % 100
if exponent == 0:
return 1
elif exponent == 1:
return base
# If base ends up with at least two zeros, then the last two digits are always two zeros.
if base == 0:
return 0
# The method is based on multiplication cycles, and differentiates cases on the last digit of the base. (cf doc)
case = base % 10
if case == 1:
return (((base // 10) * (exponent % 10)) * 10 + 1) % 100
elif case in {0, 2, 4, 6, 8}:
base_part_odd = base // 2
base_part_odd = last_digits(base_part_odd, exponent)
base_part_even = find_power_two(exponent)
return digit_multiply(base_part_odd, base_part_even)
elif case in {3, 7}:
base_square = digit_multiply(base, base)
base_fourth = digit_multiply(base_square, base_square)
exponent, rest = exponent // 4, exponent % 4
base_fourth = last_digits(base_fourth, exponent)
base_remaining = (base ** rest) % 100
return digit_multiply(base_fourth, base_remaining)
elif case == 9:
base_square = (base * base) % 100
exponent, rest = exponent // 2, exponent % 2
base_main = last_digits(base_square, exponent)
return digit_multiply(base, base_main) if rest == 1 else base_main
elif case == 5:
exponent_oddness = (exponent % 2) == 1
tens_oddness = ((base // 10) % 2) == 1
return 75 if exponent_oddness and tens_oddness else 25
def find_power_two(exponent):
"""Computes mod 100 of a power of 2"""
exponent_little = exponent % 10
exponent_big = exponent - exponent_little
res = (2 ** exponent_little) % 100
if exponent_big > 0:
eveness = (exponent_big / 10 % 2) == 0
return digit_multiply(76 if eveness else 24, res)
else:
return res % 100
def digit_multiply(first, second):
"""Computes mod 100 of a product"""
first = first % 100
second = second % 100
value = (first * second) % 100
return value
import unittest
from powers import last_digits
class TestDigitFunctions(unittest.TestCase):
def test_small_numbers(self):
for i in range(1, 20):
self.assertEqual((i ** i) % 100, last_digits(i, i))
def test_medium_numbers(self):
nbrs = [117, 768, 2339]
for i in nbrs:
self.assertEqual((i ** i) % 100, last_digits(i, i))
def test_big_numbers(self):
nbrs = [12349, 112349]
for i in nbrs:
self.assertEqual((i ** i) % 100, last_digits(i, i))
def test_exception(self):
self.assertRaises(TypeError, last_digits, "hello", 3)
self.assertRaises(TypeError, last_digits, 3, "hello")
self.assertRaises(ValueError, last_digits, -1, 3)
self.assertRaises(ValueError, last_digits, 3, -1)
if __name__ == '__main__':
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment