Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Palindrome number investigations
def digits_of(n, base=10):
"""
Split the number into its digits.
>>> digits_of(0)
[0]
>>> digits_of(123)
[1, 2, 3]
>>> digits_of(0xabc, base=16)
[10, 11, 12]
"""
if n == 0:
return [0]
digits = []
while n > 0:
n, d = divmod(n, base)
digits.append(d)
digits.reverse()
return digits
def from_digits(digits, base=10):
"""
Reconstruct an integer from its digits.
>>> from_digits([1, 2, 3])
123
>>> from_digits([10, 11, 12], base=16) == 0xabc
True
>>> all(n == from_digits(digits_of(n)) for n in range(10000))
True
"""
result = 0
power = 1
for digit in reversed(digits):
result += power * digit
power *= base
return result
def palindromes_under_naive(limit):
#>>> for limit in range(1010):
#... assert list(palindromes_under_naive(limit)) == list(palindromes_under(limit)), limit
for n in range(1, limit):
digits = digits_of(n)
if digits == list(reversed(digits)):
yield n
def palindromes_under(limit):
"""
>>> list(palindromes_under(100))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99]
>>> list(palindromes_under(30))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22]
>>> list(palindromes_under(120))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111]
"""
digit_limit = 1
while 10**digit_limit < limit:
digit_limit += 1
for num_digits in range(1, digit_limit + 1):
half_digits = (num_digits + 1) // 2
low = 10**(half_digits - 1)
high = low * 10
for half_palindrome in range(low, high):
digits = digits_of(half_palindrome)
reversed_digits = list(reversed(digits))
if num_digits % 2 == 1:
del reversed_digits[0]
n = from_digits(digits + reversed_digits)
if n >= limit:
return
#print(n)
yield n
def num_palindromes_under(limit):
"""
>>> num_palindromes_under(10)
9
>>> num_palindromes_under(100)
18
>>> num_palindromes_under(1000)
108
>>> num_palindromes_under(10000)
198
>>> num_palindromes_under(100000)
1098
>>> num_palindromes_under(1000000)
1998
"""
return len(list(palindromes_under(limit)))
if __name__ == '__main__':
# What is the sum of digits of the number of palindromes under a googol (10**100)?
power_limit = 100
total = 0
for power in range(1, power_limit + 1):
half_power = (power - 1) // 2
total += 9 * 10**half_power
print(sum(digits_of(total)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.