Skip to content

Commit

Permalink
Add Magic Number to maths algorithms (keon#730)
Browse files Browse the repository at this point in the history
* add magic number to maths

* add Magic Number to maths

* Update test_maths.py

* Updated variable names and condition statements

Co-authored-by: Nanak Bandyopadhyay <nanakbandyopadhay@hotmail.com>
  • Loading branch information
Nanak360 and Nanak Bandyopadhyay authored Oct 29, 2020
1 parent 30512d9 commit 422b1d1
Show file tree
Hide file tree
Showing 4 changed files with 76 additions and 14 deletions.
1 change: 1 addition & 0 deletions README.md
Original file line number Diff line number Diff line change
Expand Up @@ -209,6 +209,7 @@ If you want to uninstall algorithms, it is as simple as:
- [gcd/lcm](algorithms/maths/gcd.py)
- [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
- [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
- [magic_number](algorithms/maths/magic_number.py)
- [krishnamurthy_number](algorithms/maths/krishnamurthy_number.py)
- [modular_exponential](algorithms/maths/modular_exponential.py)
- [modular_inverse](algorithms/maths/modular_inverse.py)
Expand Down
3 changes: 2 additions & 1 deletion algorithms/maths/__init__.py
Original file line number Diff line number Diff line change
Expand Up @@ -19,4 +19,5 @@
from .find_primitive_root_simple import *
from .diffie_hellman_key_exchange import *
from .power import *
from .krishnamurthy_number import *
from .magic_number import *
from .krishnamurthy_number import *
36 changes: 36 additions & 0 deletions algorithms/maths/magic_number.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,36 @@
"""Magic Number
A number is said to be a magic number,
if the sum of its digits are calculated till a single digit recursively
by adding the sum of the digits after every addition.
If the single digit comes out to be 1,then the number is a magic number.
Example:
Number = 50113 => 5+0+1+1+3=10 => 1+0=1 [This is a Magic Number]
Number = 1234 => 1+2+3+4=10 => 1+0=1 [This is a Magic Number]
Number = 199 => 1+9+9=19 => 1+9=10 => 1+0=1 [This is a Magic Number]
Number = 111 => 1+1+1=3 [This is NOT a Magic Number]
The following function checks for Magic numbers and returns a Boolean accordingly.
"""


def magic_number(n):
total_sum = 0

# will end when n becomes 0
# AND
# sum becomes single digit.
while n > 0 or total_sum > 9:

# when n becomes 0 but we have a total_sum,
# we update the value of n with the value of the sum digits
if n == 0:
n = total_sum # only when sum of digits isn't single digit
total_sum = 0
total_sum += n % 10
n //= 10

# Return true if sum becomes 1
return total_sum == 1


50 changes: 37 additions & 13 deletions tests/test_maths.py
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
from algorithms.maths import (
power,power_recur,
power, power_recur,
int_to_base, base_to_int,
decimal_to_binary_ip,
euler_totient,
Expand All @@ -19,10 +19,11 @@
combination, combination_memo,
hailstone,
cosine_similarity,
magic_number,
find_order,
find_primitive_root,
alice_private_key, alice_public_key, bob_private_key, bob_public_key, alice_shared_key, bob_shared_key, diffie_hellman_key_exchange,
krishnamurthy_number,
alice_private_key, alice_public_key, bob_private_key, bob_public_key, alice_shared_key, bob_shared_key,
diffie_hellman_key_exchange, krishnamurthy_number
)

import unittest
Expand All @@ -40,13 +41,13 @@ def test_power(self):
self.assertEqual(8, power(2, 3))
self.assertEqual(1, power(5, 0))
self.assertEqual(0, power(10, 3, 5))
self.assertEqual(280380, power(2265, 1664,465465))
self.assertEqual(280380, power(2265, 1664, 465465))

def test_power_recur(self):
self.assertEqual(8, power_recur(2, 3))
self.assertEqual(1, power_recur(5, 0))
self.assertEqual(0, power_recur(10, 3, 5))
self.assertEqual(280380, power_recur(2265, 1664,465465))
self.assertEqual(280380, power_recur(2265, 1664, 465465))


class TestBaseConversion(unittest.TestCase):
Expand Down Expand Up @@ -136,6 +137,7 @@ def test_gcd_bit(self):
self.assertEqual(4, gcd_bit(8, 12))
self.assertEqual(1, gcd(13, 17))


class TestGenerateStroboGrammatic(unittest.TestCase):
"""[summary]
Test for the file generate_strobogrammatic.py
Expand Down Expand Up @@ -174,7 +176,7 @@ class TestModularInverse(unittest.TestCase):
Arguments:
unittest {[type]} -- [description]
"""
"""

def test_modular_inverse(self):
# checks if x * x_inv == 1 (mod m)
Expand All @@ -183,6 +185,7 @@ def test_modular_inverse(self):
self.assertEqual(1, 2 * modular_inverse.modular_inverse(2, 1000000007) % 1000000007)
self.assertRaises(ValueError, modular_inverse.modular_inverse, 2, 20)


class TestModularExponential(unittest.TestCase):
"""[summary]
Test for the file modular_Exponential.py
Expand All @@ -193,8 +196,8 @@ class TestModularExponential(unittest.TestCase):

def test_modular_exponential(self):
self.assertEqual(1, modular_exponential(5, 117, 19))
self.assertEqual(pow(1243, 65321, 10**9 + 7),
modular_exponential(1243, 65321, 10**9 + 7))
self.assertEqual(pow(1243, 65321, 10 ** 9 + 7),
modular_exponential(1243, 65321, 10 ** 9 + 7))
self.assertEqual(1, modular_exponential(12, 0, 78))
self.assertRaises(ValueError, modular_exponential, 12, -2, 455)

Expand Down Expand Up @@ -284,7 +287,6 @@ class TestRSA(unittest.TestCase):
"""

def test_encrypt_decrypt(self):

self.assertEqual(7, decrypt(encrypt(7, 23, 143), 47, 143))

# def test_key_generator(self): # this test takes a while!
Expand Down Expand Up @@ -326,15 +328,15 @@ def test_factorial(self):
self.assertEqual(1, factorial(0))
self.assertEqual(120, factorial(5))
self.assertEqual(3628800, factorial(10))
self.assertEqual(637816310, factorial(34521, 10**9 + 7))
self.assertEqual(637816310, factorial(34521, 10 ** 9 + 7))
self.assertRaises(ValueError, factorial, -42)
self.assertRaises(ValueError, factorial, 42, -1)

def test_factorial_recur(self):
self.assertEqual(1, factorial_recur(0))
self.assertEqual(120, factorial_recur(5))
self.assertEqual(3628800, factorial_recur(10))
self.assertEqual(637816310, factorial_recur(34521, 10**9 + 7))
self.assertEqual(637816310, factorial_recur(34521, 10 ** 9 + 7))
self.assertRaises(ValueError, factorial_recur, -42)
self.assertRaises(ValueError, factorial_recur, 42, -1)

Expand All @@ -346,6 +348,7 @@ class TestHailstone(unittest.TestCase):
Arguments:
unittest {[type]} -- [description]
"""

def test_hailstone(self):
self.assertEqual([8, 4, 2, 1], hailstone.hailstone(8))
self.assertEqual([10, 5, 16, 8, 4, 2, 1], hailstone.hailstone(10))
Expand All @@ -358,6 +361,7 @@ class TestCosineSimilarity(unittest.TestCase):
Arguments:
unittest {[type]} -- [description]
"""

def test_cosine_similarity(self):
vec_a = [1, 1, 1]
vec_b = [-1, -1, -1]
Expand All @@ -374,12 +378,13 @@ class TestFindPrimitiveRoot(unittest.TestCase):
Arguments:
unittest {[type]} -- [description]
"""

def test_find_primitive_root_simple(self):
self.assertListEqual([0], find_primitive_root(1))
self.assertListEqual([2, 3], find_primitive_root(5))
self.assertListEqual([], find_primitive_root(24))
self.assertListEqual([2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35], find_primitive_root(37))


class TestFindOrder(unittest.TestCase):
"""[summary]
Expand All @@ -388,6 +393,7 @@ class TestFindOrder(unittest.TestCase):
Arguments:
unittest {[type]} -- [description]
"""

def test_find_order_simple(self):
self.assertEqual(1, find_order(1, 1))
self.assertEqual(6, find_order(3, 7))
Expand All @@ -410,19 +416,37 @@ def test_krishnamurthy_number(self):
self.assertTrue(krishnamurthy_number(40585))


class TestMagicNumber(unittest.TestCase):
"""[summary]
Test for the file find_order_simple.py
Arguments:
unittest {[type]} -- [description]
"""

def test_magic_number(self):
self.assertTrue(magic_number(50113))
self.assertTrue(magic_number(1234))
self.assertTrue(magic_number(100))
self.assertTrue(magic_number(199))
self.assertFalse(magic_number(2000))
self.assertFalse(magic_number(500000))


class TestDiffieHellmanKeyExchange(unittest.TestCase):
"""[summary]
Test for the file diffie_hellman_key_exchange.py
Arguments:
unittest {[type]} -- [description]
"""

def test_find_order_simple(self):
self.assertFalse(diffie_hellman_key_exchange(3, 6))
self.assertTrue(diffie_hellman_key_exchange(3, 353))
self.assertFalse(diffie_hellman_key_exchange(5, 211))
self.assertTrue(diffie_hellman_key_exchange(11, 971))


if __name__ == "__main__":
unittest.main()

0 comments on commit 422b1d1

Please sign in to comment.