   Take an integer n, greater than zero.
   Form the next n of its series by reversing the digits of the current n and adding the result to the current n.
   Stop when n becomes palindromic - i.e. the digits of n in reverse order == n.


The above recurrence relation when applied to most starting numbers n = 1, 2, ... terminates in a palindrome quite quickly.



Example

If n0 = 12 we get

       12
       12 +  21 =  33,   a palindrome!

And if n0 = 55 we get

       55
       55 +  55 = 110
      110 + 011 = 121,   a palindrome!

Notice that the check for a palindrome happens   after   an addition.



Some starting numbers seem to go on forever; the recurrence relation for 196 has been calculated for millions of repetitions forming numbers with millions of digits, without forming a palindrome.

These numbers that do not end in a palindrome are called Lychrel numbers.

For the purposes of this task a Lychrel number is any starting number that does not form a palindrome within 500 (or more) iterations.



Seed and related Lychrel numbers

Any integer produced in the sequence of a Lychrel number is also a Lychrel number.

In general, any sequence from one Lychrel number might converge to join the sequence from a prior Lychrel number candidate; for example the sequences for the numbers 196 and then 689 begin:

        196
        196 +    691 =   887
        887 +    788 =  1675
       1675 +   5761 =  7436
       7436 +   6347 = 13783
      13783 +  38731 = 52514
      52514 +  41525 = 94039
       ...


        689
        689 +    986 =  1675
       1675 +   5761 =  7436
       ...

So we see that the sequence starting with 689 converges to, and continues with the same numbers as that for 196.

Because of this we can further split the Lychrel numbers into true Seed Lychrel number candidates, and Related numbers that produce no palindromes but have integers in their sequence seen as part of the sequence generated from a lower Lychrel number.



Task

   Find the number of seed Lychrel number candidates and related numbers for n in the range 1..10000 inclusive. (With that iteration limit of 500).
   Print the number of seed Lychrels found; the actual seed Lychrels; and just the number of relateds found.
   Print any seed Lychrel or related number that is itself a palindrome.


Show all output here.



References

   What's special about 196? Numberphile video.
   A023108 Positive integers which apparently never result in a palindrome under repeated applications of the function f(x) = x + (x with digits reversed).
   Status of the 196 conjecture? Mathoverflow.


on Lychrels(numberLimit, iterationLimit)
    script o
        property digits : missing value -- Digits of the current startNumber or a derived sum.
        property stigid : missing value -- Reverse thereof.
        property digitLists : missing value -- Copies of the digit lists in the current sequence.
        -- The digit lists from earlier Lychrel sequences, grouped into 1000 sublists
        -- indexed by their last three digits (+ 1) to speed up searches for them.
        property earlierDigitLists : listOfLists(1000)
        property subgroup : missing value -- Sublist picked from earlierDigitLists.
        -- Lychrel output.
        property seeds : {}
        property relateds : {}
        property palindromics : {}
 
        -- Subhandler: Has the current list of digits come up in the sequence for an earlier Lychrel?
        on isRelated()
            -- Unless it only has one digit, look for it in the appropriate subgroup of earlierDigitLists.
            set digitCount to (count my digits)
            if (digitCount > 1) then
                set i to (item -2 of my digits) * 10 + (end of my digits) + 1
                if (digitCount > 2) then set i to i + (item -3 of my digits) * 100
                set subgroup to item i of my earlierDigitLists
                -- It's faster to test this using a repeat than with 'is in'!
                repeat with i from 1 to (count my subgroup)
                    if (item i of my subgroup = digits) then return true
                end repeat
            end if
            return false
        end isRelated
    end script
 
    repeat with startNumber from 1 to numberLimit
        -- Get the number's digits and their reverse.
        set o's digits to {}
        set temp to startNumber
        repeat until (temp = 0)
            set beginning of o's digits to temp mod 10
            set temp to temp div 10
        end repeat
        set o's stigid to reverse of o's digits
        -- Note if the number itself is palindromic.
        set startNumberIsPalindrome to (o's digits = o's stigid)
 
        if (o's isRelated()) then
            -- It(s digits) occurred in the sequence for an earlier Lychrel, so it's a related Lychrel.
            set end of o's relateds to startNumber
        else
            -- Otherwise run its sequence.
            set o's digitLists to {}
            set digitCount to (count o's digits)
 
            -- Sequence loop.
            repeat iterationLimit times
                -- Add the reversed digits to those of the current number.
                set carry to 0
                repeat with i from digitCount to 1 by -1
                    set d to (item i of o's digits) + (item i of o's stigid) + carry
                    set item i of o's digits to d mod 10
                    set carry to d div 10
                end repeat
                if (carry > 0) then
                    set beginning of o's digits to carry
                    set digitCount to digitCount + 1
                end if
 
                -- If the sum's digits are palindromic, the start number's not a Lychrel.
                set o's stigid to reverse of o's digits
                set sumIsPalindrome to (o's digits = o's stigid)
                if (sumIsPalindrome) then exit repeat
                -- Otherwise, if the digits occurred in an earlier Lychrel sequence, the start number's a related Lychrel.
                set startNumberIsRelated to (o's isRelated())
                if (startNumberIsRelated) then
                    set sumIsPalindrome to false
                    exit repeat
                end if
                -- Otherwise keep a copy of the digits and go for the next number in the sequence.
                copy o's digits to end of o's digitLists
            end repeat
 
            if (not sumIsPalindrome) then
                -- No palindrome other than the start number occurred in the sequence,
                -- so the number's a Lychrel. Store it as the relevant type.
                if (startNumberIsRelated) then
                    set end of o's relateds to startNumber
                else
                    set end of o's seeds to startNumber
                end if
                if (startNumberIsPalindrome) then set end of o's palindromics to startNumber
                -- Store this sequence's digit lists based on their last three digits. There won't be any
                -- single-digit lists (they're palindromes), but there may be some with only two digits.
                repeat with thisList in o's digitLists
                    set i to (item -2 of thisList) * 10 + (end of thisList) + 1
                    set digitCount to (count thisList)
                    if (digitCount > 2) then set i to i + (item -3 of thisList) * 100
                    set end of item i of o's earlierDigitLists to thisList's contents
                end repeat
            end if
        end if
    end repeat
 
    return {seeds:o's seeds, relateds:o's relateds, palindromics:o's palindromics}
end Lychrels
 
on listOfLists(len)
    script o
        property lst : {}
    end script
    repeat len times
        set end of o's lst to {}
    end repeat
    return o's lst
end listOfLists
 
on join(lst, delim)
    set astid to AppleScript's text item delimiters
    set AppleScript's text item delimiters to delim
    set txt to lst as text
    set AppleScript's text item delimiters to astid
    return txt
end join
 
on task()
    set numberLimit to 10000
    set iterationLimit to 500
    set {seeds:seeds, relateds:relateds, palindromics:palindromics} to Lychrels(numberLimit, iterationLimit)
    set output to {"Lychrel numbers between 1 and " & numberLimit & ":", ""}
    set end of output to ((count seeds) as text) & " seed Lychrels: " & join(seeds, ", ")
    set end of output to ((count relateds) as text) & " related Lychrels"
    set end of output to ((count palindromics) as text) & " palindromic Lychrels: " & join(palindromics, ", ")
    return join(output, linefeed)
end task
 
task()