Skip to content

Instantly share code, notes, and snippets.

@outofmbufs
Created April 7, 2021 17:56
Show Gist options
  • Save outofmbufs/0438a657b26da1ed748b3ff0ae3fe522 to your computer and use it in GitHub Desktop.
Save outofmbufs/0438a657b26da1ed748b3ff0ae3fe522 to your computer and use it in GitHub Desktop.
Generate keith numbers - OEIS A007629
def iskeith(n):
"""Return True if n is a Keith number - https://oeis.org/A007629"""
if n < 10:
return False # by definition
# initial sequence seeding is the digits of n
kl = [int(d) for d in str(n)] # crude, but easy. Speed not relevant.
ksum = sum(kl)
while ksum < n:
kl.append(ksum)
ksum += ksum - kl.pop(0)
return ksum == n
def keithnumbers(start=10, stop=10000):
return (k for k in range(start, stop+1) if iskeith(k))
if __name__ == "__main__":
import unittest
class TestMethods(unittest.TestCase):
# test values copy/pasted from Online Encyclopedia of
# Integer Sequences https://oeis.org/A007629, but last
# few numbers truncated because the algorithm takes a looong
# time to reach them
OEIS_SEQ_PARTIAL = [
14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580,
3684, 4788, 7385, 7647, 7909, 31331, 34285, 34348, 55604,
62662, 86935, 93993, 120284, 129106, 147640, 156146, 174680,
183186, 298320, 355419, 694280, 925993, 1084051]
OEIS_SEQ_SLOW = [7913837, 11436171, 33445755, 44121607]
def test_keiths(self):
for k in range(1, self.OEIS_SEQ_PARTIAL[-1] + 1):
self.assertEqual(iskeith(k), k in self.OEIS_SEQ_PARTIAL)
def test_generator(self):
ks = list(self.OEIS_SEQ_PARTIAL)
kmax = ks[-1]
for k in keithnumbers(stop=kmax):
self.assertEqual(k, ks.pop(0))
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment