2
\$\begingroup\$

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292, 1292 + 2921 = 4213 4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

from time import time


def is_palindrome(number):
    """returns True for a palindrome, False otherwise."""
    to_str = str(number)
    return to_str == to_str[::-1]


def add_reverses(number, count):
    """makes a list of reverses for a number at a maximum iteration of count, breaks if palindrome found below count."""
    reverses = [number]
    for _ in range(count):
        last_number = reverses[-1]
        new_number = int(str(reverses[-1])[::-1])
        if is_palindrome(last_number + new_number):
            reverses.append(last_number + new_number)
            return reverses
        else:
            reverses.append(last_number + new_number)
    return reverses


def count_lychrel_range(number_range, count):
    """returns Lychrel numbers within number_range, assumes count is the maximum iterations for a number."""
    total = 0
    numbers_reverses = {}
    for number in range(number_range):
        numbers_reverses[number] = add_reverses(number, count)
    for number, rev_sequence in numbers_reverses.items():
        if len(rev_sequence) >= count:
            total += 1
    return total


if __name__ == '__main__':
    start_time = time()
    n = 10000
    print(f'Total Lychrel numbers below {n}: {count_lychrel_range(n, 50)}')
    print(f'Time: {time() - start_time} seconds.')
\$\endgroup\$
1
\$\begingroup\$

I like the functions you've divided up work. Good job.


def is_palindrome(number):
    """returns True for a palindrome, False otherwise."""

Its a little nickpicky, but the pep on docstrings recommends

The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".

I would change the docs here to something more like

"""Return whether a number is the same if read backwards and forwards."""

last_number = reverses[-1]
new_number = int(str(reverses[-1])[::-1])

Since last_number is reverses[-1], use it. Saves a lookup.

last_number = reverses[-1]
reversed_number = int(str(last_number[::-1]))

if is_palindrome(last_number + new_number):
    reverses.append(last_number + new_number)
    return reverses
else:
    reverses.append(last_number + new_number)

Since you have the same code in each path, and nothing before it, you can hoist it up out of the if statement

reverses.append(last_number + new_number)
if is_palindrome(last_number + new_number):
    return reverses

for _ in range(count):
    ...
    if ...:
        return reverses
    ...
return reverses

+1 for using _ as the loop variable.

This is again nitpicky, but since you have an opportunity to make this code only have one return point, why not take it?

for _ in range(count):
    last_number = reverses[-1]
    new_number = int(str(reverses[-1])[::-1])

    reverses.append(last_number + new_number)
    if is_palindrome(last_number + new_number):
        break

return reverses

def count_lychrel_range(number_range, count):
    """returns Lychrel numbers within number_range, assumes count is the maximum iterations for a number."""

Except it takes the upper bound of the range, not a number range. The doc clears it up, but just looking at the method signature I would assume you pass in the list of numbers to iterate over or a range. Since the expected call is not

count_lychrel_range(range(500, 1000), 50)

I would suggest changing the names here

def count_lychrel_numbers(upper_bound, max_iterations):

Since you only care about the length of the list, why go through all the effort of building a list of intermediate numbers from the process? In fact, you only need the length so you can compare it to the maximum number of iterations to run. Doing the test means we can just return a yes/no answer, rather than an entire list of numbers.

I think something like this inplace of add_reversed would be a little nicer.

def is_lychrel(number, max_iterations):
    """Return whether a number is a lychrel number.
    A lychrel number is one which becomes a palindrome when it is repeatedly reversed and added to itself."""
    for _ in range(max_iterations):
        reversed_number = int(str(number)[::-1])
        number += reversed_number
        if is_palindrome(number):
            return True
    return False

Then count_lychrel_numbers can be a simple loop

def count_lychrel_numbers(upper_bound, max_iterations):
    """..."""
    total = 0
    for number in range(upper_bound):
        if is_lychrel(number, max_iterations):
            total += 1
    return total

Or if you want to use sum

def count_lychrel_numbers(upper_bound, max_iterations):
    """..."""
    return sum(1 for number in range(upper_bound) if is_lychrel(number, max_iterations))

As a bonus, you can see that "new_number" is reversed twice. Once in is_palindrome and once in add_reverses/is_lychrel. Can you reduce it down to just one reverse without bloating the code?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy