notes.html

problem 55 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
    This problem revolves around a simple iterative transformation: take a number, reverse its decimal digits, add the two together, and check whether the result is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Palindromic_number" rel="noopener noreferrer" target="_blank">palindromic number</a> - a number that reads the same forwards and backwards, like 121 or 7337. If the sum is not a palindrome, we repeat the reverse-and-add on the new value. A <a class="reference-source" href="https://en.wikipedia.org/wiki/Lychrel_number" rel="noopener noreferrer" target="_blank">Lychrel number</a> is one that, conjecturally, never reaches a palindrome by this process. The mathematical subtlety is that no number has ever been *proven* to be Lychrel; in base 10 the property is, as far as anyone knows, undecidable. What rescues the problem is the bounded budget the statement supplies: every number below ten thousand either reaches a palindrome within fifty iterations, or has resisted all computation ever attempted. That lets me redefine "Lychrel" operationally as "did not become a palindrome within 50 reverse-and-add steps," turning an open mathematical question into a finite, well-defined search.
  </p>
<p>
    The one engineering wrinkle is the magnitude of the intermediate values. Each reverse-and-add roughly doubles the value and can add a digit, so after dozens of steps the numbers overflow 64-bit integers - the statement itself cites a 28-digit result for 10677. Any correct solution therefore needs <a class="reference-source" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic" rel="noopener noreferrer" target="_blank">arbitrary-precision arithmetic</a>. The total cost is O(N * I * D), where N = 10,000 is the search limit, I = 50 is the iteration cap, and D is the digit-count of the largest intermediate (comfortably under 30). Because D stays tiny, the computation is effectively linear in N and finishes in milliseconds.
  </p>
<h3>Solution Approach</h3>
<h4>Bounded Iterative Reverse-and-Add with Big-Integer Arithmetic (Python and C)</h4>
<p>
    Both solutions share one algorithm. For each candidate <code>i</code> from 1 to the limit I call <code>is_lychrel</code>, which performs up to <code>max_iterations</code> rounds of reverse-and-add. In each round I first apply the operation, then test the result for palindromicity. The ordering matters: a starting value that is itself a palindrome - 4994 is the smallest example - can still be a Lychrel number, so I must judge the *result* of the step, not the seed. If any step yields a palindrome, the number is not Lychrel and I return false; if the loop exhausts its budget, I return true.
  </p>
<p>
    In Python the code is short because integers are arbitrary-precision natively. I reverse the digits by converting to a string, reversing it with the slice <code>[::-1]</code>, and parsing back with <code>int(...)</code>. The palindrome test reuses the same idea: a number is a palindrome exactly when <code>str(number) == str(number)[::-1]</code>. The counting in <code>solve</code> is a single <code>sum</code> over a generator of boolean results.
  </p>
<p>
    In C there is no built-in big integer, so I defined a fixed-width <code>BigNum</code>: an array of decimal digits stored little-endian (least significant digit at index 0) with an explicit length. I chose base 10 rather than a larger base on purpose - the palindrome test operates on decimal digits, so storing in base 10 means I never convert between an arithmetic base and a display base. <code>bignum_add_reverse</code> computes <code>a + reverse(a)</code> in a single pass: for index <code>i</code> it adds <code>a.digits[i]</code> to <code>a.digits[n-1-i]</code> with carry, because the little-endian position <code>i</code> is exactly the big-endian position <code>n-1-i</code> of the same number. This avoids materialising a separate reversed copy. A 128-digit buffer is far more than 50 iterations starting below 10,000 will ever need. The palindrome check just compares symmetric digit pairs. Both implementations agree on the answer, 249.
  </p>
</article>