Perl Weekly Challenge 137: Lychrel Number

This is a bit of a peculiar task. We are asked to find Lychrel numbers, yet there are (in base 10), no known Lychrel numbers. For most of the numbers below 1,000, it is known they are not Lychrel. The numbers which are not known to be Lychrel form sequence A023108 in the OEIS. There are 13 numbers below 1,000 which are not known to be Lychrel; of which two are so-called "seeds": 196, and 986. All the other unknowns quickly convergence to the same sequence as is generated when starting from 196.

This makes that the extra condition (at most 500 iterations, or reaching 10,000,000 or higher) is of interest. But there are some oddities. First, it causes some numbers known to not be a Lychrel, to be reported to be one. Take for instance the number 89. If we reverse it and add it to itself, and do this process 24 times, we reach 8,813,200,023,188, which is a palindrome. Which makes 89 not a Lychrel number. However, 8,813,200,023,188 exceeds 10,000,000, so the wanted program will report this as a Lychrel number. In fact, there are 42 numbers below 1,000 whose sequence gets terminated because it reaches 10,000,000. Of those 42, 29 are known not to be Lychrel numbers. It's not until we increase the cut-off to 8,813,200,023,189 that we only report 13 numbers to be Lychrel numbers: exactly the 13 numbers below 1,000 of which it is not known whether they are Lychrel numbers or not.

Second, the limit of 500 iterations is pointless. The numbers grow rapidly, and for each of the numbers up to 1000, we reach a number which is either a palindrome or which is at least 10,000,000 in at most 12 steps. Even if we raise the cut-off value to 8,813,200,023,189, it never takes more than 27 iterations to either reach a palindrome, or to exceed the cut-off value.

Here is a plot of how many iterations we need for the numbers from 10 to 1000 to find the answer. Points in green mean the number converges to a palindrome less than 10,000,000. Each of them is reached in nine iterations or less. Points in red reach a number exceeding 10,000,000.

So, we might as well forget about the 500 iterations limit; which is exactly what we do in our solutions.

Enter a number below, hit the calculate button, and we tell you whether the sequence reaches a palindrome, or whether it hits one of the (configurable) limits: max iterations, or the cut-off value.

In Perl, it's very easy to reverse a number. reverse reverses a string, but in Perl conversions between numbers and strings happen automatically.

A function to check whether a number is a Lychrel number (according to the definition in the challenge, not the definition the rest of the world uses) is easy. As stated above, we don't check for the number of iterations. Which leaves us with two checks:

• If the number exceeds 10,000,000, we return true.
• If the number equals its reverse, we return false.
• Else, we recurse.

This gives us:

sub is_lychrel ($n) {
    $n >= 10_000_000   ? 1
  : $n eq reverse ($n) ? 0
  : is_lychrel ($n + reverse $n)}

Find the full program on GitHub.

Most other languages either don't have a build in reverse method, or don't automatically convert between strings and numbers. In those cases, we need to write our own reverse method. This is a pretty simple process, and we use the same algorithm in each language. For instance, in Pascal, we use:

function reverse (num: Longint): Longint;
    var
        rev: Longint;

    begin
        rev := 0;
        while num > 0 do begin
            rev := rev * 10;
            rev := rev + (num mod 10);
            num := num div 10;
        end;
        reverse := rev;
    end;

It boils down to repeatedly chopping off the last digit of num (which is our input value), and adding it to rev (the return value). But by first multiplying rev by 10 before adding a new digit, we end up with the wanted result.

The check function then looks like:

function ly (num: Longint): integer;
    begin
        if num >= 10000000 then
            ly := 1
        else if num = reverse (num) then
            ly := 0
        else 
            ly := ly (num + reverse (num))
    end;

Find the full program on GitHub.