   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.


 
function Test-Palindrome ( [String]$String )
    {
    #  Default value
    $IsPalindrome = $True
 
    #  For each position in the string from the start to the middle
    ForEach ( $Index in ( 0..($String.Length -shr 1 ) ) )
        {
        #  Check if the character at this position matches the corresponding character at the other end
        $IsPalindrome = $IsPalindrome -and $String[$Index] -eq $String[$String.Length - $Index - 1]
        }
 
    return $IsPalindrome
    }
 
function Get-LychrelNumbers ( [int]$Upto, [int]$IterationLimit = 500 )
    {
    #  Initialize empty collections
    #  (More typically, PowerShell will use Arrays, but we are using
    #   ArrayLists here to optimize speed and memory usage.)
    $Seeds       = New-Object System.Collections.ArrayList
    $Related     = New-Object System.Collections.ArrayList
    $Palindromes = New-Object System.Collections.ArrayList
 
    #  For each integer in the test range...
    ForEach ( $N in [bigint]1..[bigint]$Upto )
        {
        #  If N was already identified as a related Lychrel in another
        #  Lychrel series, we don't need to test it
        If ( $N -notin $Related )
            {
            #  Default value
            $IsRelated = $False
 
            #  Initialize empty collection
            $NSeries = New-Object System.Collections.ArrayList
 
            #  Starting at N
            $S = $N
 
            #  Convert S to a string for testing and processing
            $SString = $S.ToString()
 
            #  For each iteration up to the maximum...
            #  (Generally we would not use ForEach with Break for a loop with
            #   these requirements, but this script is optimized for speed
            #   and ForEach ( $x in $y ) is the fastest loop in PowerShell.)
            ForEach ( $i in 1..$IterationLimit )
                {
                #  Add the reverse of S to S
                $S += [bigint]($SString[($SString.Length)..0] -join '' )
 
                #  If S appears in the series of a smaller seed Lychrel
                If ( $S -in $Related )
                    {
                    #  S is a related Lychrel; exit processing loop
                    $IsRelated = $True
                    Break
                    }
 
                #  Convert S to a string for testing and processing
                $SString = $S.ToString()
 
                If ( Test-Palindrome $SString )
                    {
                    Break
                    }
 
                #  Add S to the series we are testing
                #  (for possible inclusion as a related number if N turns out to be a seed)
                $NSeries.Add( $S )
                }
 
            #  If series did not terminate before the iteration limit...
            #  (Including if we stopped early because it join up with an earlier non-terminating series)
            If ( $IsRelated -or $i -eq $IterationLimit )
                {
                #  Add everything in the series above N to the list of related Lychrel numbers
                $Related.AddRange( $NSeries )
 
                #  If N is a related Lychrel number, add it to the list
                If ( $IsRelated         ) { $Related.    Add( $N ) }
 
                #  Otherwise add it to the list of Seed Lychrel numbers
                Else                      { $Seeds.      Add( $N ) }
 
                #  If N is a palindrome, add it to the list of palindrome Lychrel numbers
                If ( Test-Palindrome $N ) { $Palindromes.Add( $N ) }
                }
            }
        }
 
    #  Convert the various arraylists of big integers to arrays of integers and assign
    #  them as properties of a custom return object. Filter out those Related Lychrel
    #  numbers which exceed our search range.
    $LychrelNumbers = [pscustomobject]@{
            Seeds       = [int[]]$Seeds
            Related     = [int[]]$Related.Where{ $_ -le $Upto }
            Palindromes = [int[]]$Palindromes }
 
    return $LychrelNumbers
    }
 