Lychrel numbers

Lychrel numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

1. Take an integer n, greater than zero.
2. Form the next n of its series by reversing the digits of the current n and adding the result to the cuurent n.
3. 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, for example if n₀ = 12 we get

12
12 + 21 = 33, a palindrome!

And if n₀ = 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 for ever; 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.

Any integer produced in the sequence of a Lychrel number is also a likely to be a Lychrel number, so we can further split the Lychrel numbers into Lychrel numbers, and Related numbers that produce no palindromes, but has integers in its sequence seen as part of the sequence generated from a lower Lychrel number.

Task

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

Show all output here.

Python

<lang python>def add_reverse(num, max_iter=1000):

   i, nums = 0, {num}
   while True:
       i, num = i+1, num + reverse_int(num)
       nums.add(num)
       if reverse_int(num) == num or i >= max_iter:
           break
   return nums
   

1. @functools.lru_cache(maxsize=2**20)

def reverse_int(num):

   return int(str(num)[::-1])

def split_roots_from_relateds(roots_and_relateds):

   roots = roots_and_relateds.copy()
   i = 1
   while i < len(roots):
       this = roots[i]
       if any(this.intersection(prev) for prev in roots[:i]):
           del roots[i]
       else:
           i += 1
   root = [min(each_set) for each_set in roots]
   related = [min(each_set) for each_set in roots_and_relateds]
   related = [n for n in related if n not in root]
   return root, related

def find_lychrel(maxn, max_reversions):

   'Lychrel number generator'
   series = [add_reverse(n, max_reversions*2) for n in range(1, maxn + 1)]
   roots_and_relateds = [s for s in series if len(s) > max_reversions]
   return split_roots_from_relateds(roots_and_relateds)

if __name__ == '__main__':

   maxn, reversion_limit = 10000, 500
   print("Calculations using n = 1..%i and limiting each search to 2*%i reverse-digits-and-adds"
         % (maxn, reversion_limit))
   lychrel, l_related = find_lychrel(maxn, reversion_limit)
   print('  Number of Lychrel numbers:', len(lychrel))
   print('    Lychrel numbers:', ', '.join(str(n) for n in lychrel))
   print('  Number of Lychrel related:', len(l_related))
   #print('    Lychrel related:', ', '.join(str(n) for n in l_related))
   pals = [x for x in lychrel + l_related  if x == reverse_int(x)]
   print('  Number of Lychrel palindromes:', len(pals))
   print('    Lychrel palindromes:', ', '.join(str(n) for n in pals))</lang>

Output:

Calculations using n = 1..10000 and limiting each search to 2*500 reverse-digits-and-adds
  Number of Lychrel numbers: 5
    Lychrel numbers: 196, 879, 1997, 7059, 9999
  Number of Lychrel related: 244
  Number of Lychrel palindromes: 3
    Lychrel palindromes: 9999, 4994, 8778