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

 

 

Subtracting Large Numbers as Strings in Pascal

Pascal's built-in numeric types (like Integer or Int64) have size limits. If you need to subtract numbers that are too large to fit in these types, you must represent them as strings and implement the subtraction manually, digit by digit.

General Approach

1. Normalize the Strings

   • Remove leading zeros.

   • Pad the shorter string with leading zeros so both strings have the same length.

2. Subtract Digit by Digit

   • Start from the rightmost digit (least significant).

   • Subtract each digit, borrowing from the next left digit if needed.

   • Keep track of the borrow and adjust subsequent digits accordingly.

3. Handle Negative Results

   • If the first number is smaller, swap and note the result will be negative.

4. Remove Leading Zeros from Result

Sample Pascal Implementation

Below is a simplified version of how you can subtract two big numbers represented as strings in Pascal:

 

function SubtractBigNumbers(a, b: string): string;

var

  i, borrow, adiff, digitA, digitB: integer;

  resultStr: string;

  negative: boolean;

begin

  // Step 1: Normalize lengths

  while length(a) < length(b) do a:= '0' + a;

  while length(b) < length(a) do b:= '0' + b;

  // Step 2: Determine if result will be negative

  negative:= false;

  if a < b then begin

    negative:= true;

    // Swap a and b

    result:= SubtractBigNumbers(b, a);

    if result <> '0' then

      result:= '-' + result;

      begin

        result:= result;

        exit; end;

  end;

  borrow:= 0;

  resultStr:= '';

  // Step 3: Subtract digit by digit

  for i := length(a) downto 1 do begin

    digitA:= ord(a[i]) - ord('0') - borrow;

    digitB:= ord(b[i]) - ord('0');

    if digitA < digitB then begin

      digitA:= digitA + 10;

      borrow:= 1;

    end else

      borrow:= 0;

    adiff:= digitA - digitB;

    resultStr:= inttoascii(adiff + ord('0'),1) + resultStr;

  end;

  // Step 4: Remove leading zeros

  while (length(resultStr) > 1) and (resultStr[1] = '0') do

    delete(resultStr, 1, 1);

  {SubtractBigNumbers} result:= resultStr;

end;