Lychrel number
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:
- 294+492=786
- 786+687=1473
- 1473+3741=5214
- 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/.
Comments
Post a Comment