maths.keith_number

== Keith Number (Repfigit Number) == A Keith number (also known as a repfigit number, short for “repetitive Fibonacci-like digit”) is a natural number n with d >= 2 decimal digits such that when a sequence is formed starting with the d digits of n and each subsequent term is the sum of the preceding d terms, the number n itself appears in the sequence.

For example, 197 is a 3-digit number (d = 3):

Initial terms: 1, 9, 7 Next term: 1 + 9 + 7 = 17 Next term: 9 + 7 + 17 = 33 Next term: 7 + 17 + 33 = 57 Next term: 17 + 33 + 57 = 107 Next term: 33 + 57 + 107 = 197 (Matches 197! So 197 is a Keith number).

The first few Keith numbers are: 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385…

References: - https://en.wikipedia.org/wiki/Keith_number - https://oeis.org/A007629

Functions

find_keith_numbers(→ list[int])	Find and return all Keith numbers up to a specified limit.
is_keith_number(→ bool)	Check if a given integer is a Keith number.

Module Contents

maths.keith_number.find_keith_numbers(limit: int) → list[int]

Find and return all Keith numbers up to a specified limit.

Complexity Analysis:

• Time Complexity: O(limit * log(limit))

• Space Complexity: O(k) where k is the number of Keith numbers found.

Args:

limit: The upper bound (inclusive) up to which to search for Keith numbers.

Returns:

A list of Keith numbers less than or equal to limit.

Raises:

TypeError: If limit is not an integer. ValueError: If limit is less than 10.

Examples:

>>> find_keith_numbers(100)
[14, 19, 28, 47, 61, 75]
>>> find_keith_numbers(200)
[14, 19, 28, 47, 61, 75, 197]
>>> find_keith_numbers(10)
[]

Type and value errors: >>> find_keith_numbers(9) Traceback (most recent call last):

…

ValueError: limit must be an integer greater than or equal to 10 >>> find_keith_numbers(10.5) Traceback (most recent call last):

…

TypeError: limit must be an integer >>> find_keith_numbers(False) Traceback (most recent call last):

…

TypeError: limit must be an integer

maths.keith_number.is_keith_number(number: int) → bool

Check if a given integer is a Keith number.

A Keith number is an integer greater than or equal to 10 that appears in the Fibonacci-like sequence generated by its digits. Single-digit numbers are excluded by mathematical convention.

Complexity Analysis:

• Time Complexity: O(d * k) where d is the number of digits of number and k is the number of terms until the sequence reaches or exceeds the number. Since the terms grow exponentially, k = O(log(number)).

• Space Complexity: O(d) auxiliary space to store the previous d terms.

Args:

number: The integer to test.

Returns:

True if number is a Keith number, False otherwise.

Raises:

TypeError: If number is not an integer.

Examples:

Known 2-digit Keith numbers: >>> is_keith_number(14) True >>> is_keith_number(19) True >>> is_keith_number(28) True >>> is_keith_number(47) True >>> is_keith_number(61) True >>> is_keith_number(75) True

Known 3-digit and 4-digit Keith numbers: >>> is_keith_number(197) True >>> is_keith_number(742) True >>> is_keith_number(1104) True >>> is_keith_number(1537) True

Non-Keith numbers: >>> is_keith_number(10) False >>> is_keith_number(12) False >>> is_keith_number(25) False >>> is_keith_number(100) False

Edge cases (single-digit and non-positive integers): >>> is_keith_number(9) False >>> is_keith_number(1) False >>> is_keith_number(0) False >>> is_keith_number(-14) False

Type validation: >>> is_keith_number(14.0) Traceback (most recent call last):

…

TypeError: number must be an integer >>> is_keith_number(“14”) Traceback (most recent call last):

…

TypeError: number must be an integer >>> is_keith_number(True) Traceback (most recent call last):

…

TypeError: number must be an integer >>> is_keith_number(None) Traceback (most recent call last):

…

TypeError: number must be an integer