Lychrel number

#programming#mathematics#algorithms#numbertheory

A Lychrel number is a natural number that cannot form a palindrome through the iterative process of reversing its digits and adding the resulting numbers. This process is often referred to as the 196-algorithm, named after the most famous number associated with it.
To determine if a number is a Lychrel number in Pascal, we implement a string-based approach to handle large numbers generated during iterations. Here's a structured solution:

Key Components

• String Reversal: Reverse the digits of a number represented as a string.
• String Addition: Add two large numbers (as strings) to avoid integer overflow.
• Palindrome Check: Verify if a string is a palindrome.
• Iteration Loop: Perform up to 500 iterations of reversal and addition, checking for palindromes.

Pascal Implementation

var
  Seeds : array of LongInt;

function ReverseString(s: string): string;
var i: integer;
begin
  Result:= '';
  for i:= Length(s) downto 1 do
    Result:= Result + s[i];
end;

function AddStrings(a, b: string): string;
var i, sum, carry: integer;
begin
  carry:= 0;
  Result:= '';
  while Length(a) < Length(b) do a:= '0' + a;
  while Length(b) < Length(a) do b:= '0' + b;
  for i:= Length(a) downto 1 do begin
    sum:= (Ord(a[i])- Ord('0'))+ (Ord(b[i])- Ord('0'))+ carry;
    carry:= sum div 10;
    Result:= inttoAscii((sum mod 10)+ Ord('0'),1)+ Result;
  end;
  if carry > 0 then Result:= inttoascii(carry + Ord('0'),1)+ Result;
  while (Length(Result) > 1) and (Result[1] = '0') do Delete(Result,1,1);
end;

function IsPalindrome(s: string): boolean;
var i: integer;
begin
  for i:= 1 to Length(s) div 2 do
    if s[i] <> s[Length(s)-i+1] then begin result:= false Exit; end;
  Result:= True;
end;


//correctly identifies Lychrel numbers like 196 as bool
var lfound: string;
function IsLychrel(n: Integer; maxIterations: Integer): Boolean;
var numStr, reversedStr: string;
    i: integer;
begin
  numStr:= IntToStr(n);
  processmessagesOFF;
  for i:= 1 to maxIterations do begin
    reversedStr:= ReverseString(numStr);
    numStr:= AddStrings(numStr, reversedStr);
    writeln(itoa(i)+':'+numstr)
    if IsPalindrome(numStr) then begin write(numstr+' steps: '+itoa(i)); 
                              lfound:= numstr; result:= false Exit; 
                            end;
  end;
  processmessagesON;
  Result:= True;
end;

Explanation

• String Handling: Numbers are processed as strings to manage arbitrarily large values!
• Reversal and Addition: Each iteration reverses the current number and adds it to the original, ensuring correct handling of leading zeros.
• Palindrome Check: Compares the string to its reverse after each addition.
• Efficiency: The algorithm stops early if a palindrome is detected or after 500 iterations, whichever comes first.

This approach correctly identifies Lychrel numbers like 196, which do not form palindromes within the iteration limit.

// Example usage
const maxIter = 500;
//number= 196;  as proof for never finding!
var number: integer;

  number:= 294;        //196  is! 295
  if IsLychrel(number, maxIter) then
    Writeln(itoa(number)+' is a Lychrel number.')
  else
    Writeln(itoa(number)+' is not a Lychrel number, cause we found: '+lfound);

1:786
2:1473
3:5214
4:9339
9339 steps: 4
294 is not a Lychrel number, cause we found: 9339
mX5🐞 executed: 24/04/2025 20:38:19 Runtime: 0:0:2.242 Memload: 75% use

294 explained in 4 steps:

1. 294+492=786
2. 786+687=1473
3. 1473+3741=5214
4. 5214+4125=9339!

The script can be found at:
1398_Lychrel_numbers12_uc.txt

Another example, if we reverse and add 15 we get 66, (because 15 + 51 =66)
The term Lychrel was coined by the computer scientist Wade Van Landingham, who has spent a lot of effort in the search to determine whether or not 196 is a Lychrel number and created a website dedicated to the search p196.org/.