Created
October 20, 2014 21:06
-
-
Save nooodl/fa8a9019233091f64c91 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# We could iterate over factors and check for palindromes in their products, | |
# but this is slower than iterating over palindromes and trying to split them | |
# up[1]: the approach used here examines possible solutions in descending | |
# order, so we always find the biggest one first. This allows us to exit early. | |
# | |
# Either way, here's a definition for `is_palindrome` that ended up being | |
# unnecessary: | |
# | |
# def is_palindrome(x): | |
# """Is the given positive integer x a palindromic number?""" | |
# s = str(x) | |
# return s == s[::-1] | |
def descending_sub_n_digit_palindromes(n): | |
"""Returns all palindromes with <= n digits, in descending order.""" | |
# The digits of an n-digit palindrome look like this: | |
# | |
# * If n is even we want the form abcddcba. | |
# ==== <- ceil(n / 2) digits | |
# * If n is odd we want the form abcdedcba. | |
# ===== <- ceil(n / 2) digits | |
# | |
# Either way, we count down ((n + 1) // 2)-digit numbers and append their | |
# reverse string values; if n is odd, don't count the center digit twice. | |
while n >= 0: | |
k = (n + 1) // 2 | |
highest = 10 ** k - 1 | |
lowest = highest // 10 | |
for x in range(highest, lowest, -1): | |
s_x = str(x) # "abcde" | |
rev = s_x[::-1] # "edcba" | |
# For odd n, skip the doubled center digit: | |
if n % 2 == 1: | |
rev = rev[1:] # "dcba" | |
yield int(s_x + rev) # "abcdedcba" | |
n -= 1 | |
def find_largest_palindrome(n): | |
"""Finds the largest palindrome that can be written as the sum of two | |
n-digit numbers.""" | |
# Highest possible n-digit factor. | |
highest = 10 ** n - 1 | |
# The product of two n-digit numbers has no more than 2n digits: | |
for p in descending_sub_n_digit_palindromes(2 * n): | |
if p > highest ** 2: | |
continue | |
# Try to split p up into two factors. We want a >= p // a, otherwise | |
# we consider each pair twice; this is why we only count down to | |
# sqrt(p) inclusive. Since | |
# | |
# highest // 10 < sqrt(p) <= p // a <= a <= highest, | |
# | |
# both numbers returned will have n digits. | |
for a in range(highest, int(p ** .5) - 1, -2): | |
if p % a == 0: | |
return (a, p // a) | |
def print_largest_palindrome(n): | |
"""Formatting wrapper around find_largest_palindrome.""" | |
a, b = find_largest_palindrome(n) | |
print('Largest palindrome found! {} x {} = {}'.format(a, b, a * b)) | |
n = int(input('How many digits in each factor? ')) | |
print_largest_palindrome(n) | |
# [1]: (In fact, this appears to be the fastest palindrome product finding | |
# function out there! On a slow laptop even find_largest_palindrome(7) | |
# takes less than two seconds; results from various Project Euler blogs | |
# across the internet seem to lie closer to 30 seconds, up to a minute. | |
# The algorithm runs in O(sqrt(10^n)) time, I think, but I might be wrong, | |
# so don't grade me on that statement.) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment