fork download
copy 
  1. # Digital root. (2.00)
  2. # @see j9kUG0
  3.  
  4. import sys
  5. import unittest
  6. import timeit
  7. import random
  8.  
  9. # Formal definition.
  10. # A natural number n is a digital root if it is a fixed point for digit_sum
  11. # (which occurs if n equals digit_sum(n)).
  12. # @see en.wikipedia.org/wiki/Digital_root
  13.  
  14. def digital_root_1(n: int) -> int:
  15.     if n < 0:
  16.         raise ValueError('n must be non-negative')
  17.     return fixed_point(digit_sum, n, lambda x, y: x == y)
  18.  
  19. def fixed_point(f, guess, equal):
  20.     while not equal(guess, result := f(guess)):
  21.         guess = result
  22.     return guess
  23.  
  24. def digit_sum(n: int) -> int:
  25.     a = 0
  26.     while n > 0:
  27.         n, a = n // 10, a + n % 10
  28.     return a
  29.  
  30. # Direct formulas.
  31.  
  32. def digital_root_2(n: int) -> int:
  33.     if n < 0:
  34.         raise ValueError('n must be non-negative')
  35.     if n == 0:
  36.         return 0
  37.     n %= 9
  38.     return n if n != 0 else 9
  39.  
  40. def digital_root_3(n: int) -> int:
  41.     if n < 0:
  42.         raise ValueError('n must be non-negative')
  43.     if n == 0:
  44.         return 0
  45.     return 1 + (n - 1) % 9
  46.  
  47. def digital_root_4(n: int) -> int:
  48.     if n < 0:
  49.         raise ValueError('n must be non-negative')
  50.     if n == 0:
  51.         return 0
  52.     return n - (n - 1) // 9 * 9 # flooring division
  53.  
  54. # Test.
  55.  
  56. class TestDigitalRoot(unittest.TestCase):
  57.     def _test_digital_root(self, f):
  58.         with self.assertRaisesRegex(ValueError, 'negative'):
  59.             f(-1)
  60.         self.assertEqual(f(0), 0)
  61.         for i in range(1, 10):
  62.             for j in range(3):
  63.                 self.assertEqual(f(i+9*j), i)
  64.  
  65.     def test_digital_root_1(self):
  66.         self._test_digital_root(digital_root_1)
  67.  
  68.     def test_digital_root_2(self):
  69.         self._test_digital_root(digital_root_2)
  70.  
  71.     def test_digital_root_3(self):
  72.         self._test_digital_root(digital_root_3)
  73.  
  74.     def test_digital_root_4(self):
  75.         self._test_digital_root(digital_root_4)
  76.  
  77. def benchmark_digital_root(n):
  78.     def benchmark(f):
  79.         def bench():
  80.             for i in range(n):
  81.                 f(10**(i%10)*2-1) # 1, 19, 199, ...
  82.         return f.__name__, timeit.timeit(bench, number=1)
  83.  
  84.     fs = [
  85.         digital_root_1,
  86.         digital_root_2,
  87.         digital_root_3,
  88.         digital_root_4
  89.     ]
  90.  
  91.     for name, t in map(benchmark, fs):
  92.         print(f'{name}: {t:.6f}s')
  93.  
  94. if __name__ == '__main__':
  95.     print('Running unit tests ...', file=sys.stderr)
  96.     unittest.main(verbosity=2, exit=False)
  97.     print('\nBenchmarking ...')
  98.     benchmark_digital_root(10000)
Success #stdin #stdout #stderr 0.42s 20504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Benchmarking ...
digital_root_1: 0.016695s
digital_root_2: 0.002750s
digital_root_3: 0.002829s
digital_root_4: 0.003249s
stderr
copy 
Running unit tests ...
test_digital_root_1 (__main__.TestDigitalRoot.test_digital_root_1) ... ok
test_digital_root_2 (__main__.TestDigitalRoot.test_digital_root_2) ... ok
test_digital_root_3 (__main__.TestDigitalRoot.test_digital_root_3) ... ok
test_digital_root_4 (__main__.TestDigitalRoot.test_digital_root_4) ... ok

----------------------------------------------------------------------
Ran 4 tests in 0.001s

OK
https://ideone.com/U95til
language:
Python 3 (python  3.12)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!