Problem 55: Lychrel Numbers

View on Project Euler

Project Euler Problem 55 Solution

EulerSolve provides an optimized solution for Project Euler Problem 55, Lychrel Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For each integer \(1 \le n < 10{,}000\), repeatedly apply the decimal reverse-and-add map. If none of the first 50 generated values is a palindrome, the starting number is counted as a Lychrel number for the purpose of this problem. The task is therefore a finite counting problem: determine how many starting values stay non-palindromic for all 50 prescribed steps. The important subtlety is that this definition is operational rather than absolute. Some starting values, such as 196, are famous unresolved cases in the unrestricted reverse-and-add process. Here we do not need to decide whether they are truly Lychrel in an infinite sense; we only need to test the first 50 iterations exactly. Mathematical Approach Let \(R(x)\) denote the decimal reversal of \(x\). If \(x\) has digits \(a_{d-1}a_{d-2}\dots a_1a_0\), then $$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i},$$ with the usual convention that leading zeros in the reversed digit string disappear numerically. Starting from \(x_0=n\), the process is $$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$ We write \(P(x)\iff x=R(x)\) for the palindrome predicate. A starting value is counted precisely when $$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$ The Right State Space Each starting number generates a deterministic orbit under the map \(x\mapsto x+R(x)\)....

Detailed mathematical approach

Problem Summary

For each integer \(1 \le n < 10{,}000\), repeatedly apply the decimal reverse-and-add map. If none of the first 50 generated values is a palindrome, the starting number is counted as a Lychrel number for the purpose of this problem. The task is therefore a finite counting problem: determine how many starting values stay non-palindromic for all 50 prescribed steps.

The important subtlety is that this definition is operational rather than absolute. Some starting values, such as 196, are famous unresolved cases in the unrestricted reverse-and-add process. Here we do not need to decide whether they are truly Lychrel in an infinite sense; we only need to test the first 50 iterations exactly.

Mathematical Approach

Let \(R(x)\) denote the decimal reversal of \(x\). If \(x\) has digits \(a_{d-1}a_{d-2}\dots a_1a_0\), then

$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i},$$

with the usual convention that leading zeros in the reversed digit string disappear numerically. Starting from \(x_0=n\), the process is

$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$

We write \(P(x)\iff x=R(x)\) for the palindrome predicate. A starting value is counted precisely when

$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$

The Right State Space

Each starting number generates a deterministic orbit under the map \(x\mapsto x+R(x)\). Because the Project Euler condition only asks about the first 50 images, there is no need for probabilistic heuristics or conjectures about infinite behavior. The problem reduces to examining 9,999 independent trajectories inside the finite horizon \(t\le 50\).

Formally, the set being counted is

$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$

This formulation matches the implementations exactly: every number below \(10^4\) is tested separately, and the moment a palindrome appears the trajectory is removed from the count.

Why the Starting Number Does Not End the Search

The palindrome test is applied after a reverse-and-add step, not to the original input. That detail matters. A number such as \(121\) is already palindromic, but the relevant sequence is

$$121 \to 121+121=242,$$

so it is still processed through one iteration and then succeeds immediately. The decision rule depends on the generated values \(x_1,x_2,\dots\), not on \(x_0\) itself.

A Useful Digit-Growth Bound

If \(x\) has \(d\) decimal digits, then \(x<10^d\) and also \(R(x)<10^d\). Hence

$$x+R(x)<2\cdot 10^d<10^{d+1}.$$

So a single reverse-and-add step can increase the digit count by at most one. Since every input in this problem has at most four digits, after at most 50 steps every intermediate value has at most \(4+50=54\) digits.

This bound explains why manual decimal-string arithmetic is sufficient. The values can exceed native 64-bit types, but they never become remotely too large for a carry-based string implementation.

Worked Examples

The standard non-Lychrel example from the statement is

$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$

A palindrome appears at the third generated value, so 349 is excluded from \(\mathcal{L}_{50}\).

A simpler checkpoint is \(47\):

$$47 \to 47+74=121.$$

That becomes palindromic immediately. By contrast, 196 begins

$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$

and does not reach a palindrome within the first 50 iterations. Therefore it is counted by the problem's finite rule, regardless of the unresolved infinite version of the question.

How the Code Works

Decimal-String Arithmetic Instead of Big Integers

The C++, Python, and Java implementations all keep the current iterate as a decimal string. Reversal is obtained by reversing that string, and addition is performed digit by digit from right to left with an explicit carry. This is ordinary schoolbook addition, and it avoids any dependence on big-integer libraries.

Palindrome detection is a direct two-ended comparison on the current string. Because all intermediate values stay within the 54-digit bound above, this representation is simple, portable, and fully adequate in all three languages.

Testing One Start, Then Sweeping the Full Range

For a single starting value, the implementation repeats the same loop at most 50 times: reverse, add, test for palindromicity, and stop early if a palindrome appears. A starting value is counted only if the loop survives all 50 rounds without success.

After that, the outer routine applies the test to every integer from 1 up to 9999 and counts the survivors. The default parameters match the Project Euler statement, but the programs also allow the upper limit and the iteration cap to be changed from the command line. Before printing the final count, they verify familiar examples such as 47 and 349 to confirm that the rule has been implemented correctly.

Complexity Analysis

Let \(L=9999\), let \(S=50\), and let \(D\) be the maximum number of digits seen during the run. Each iteration performs one reversal, one addition with carry, and one palindrome check, all linear in the current digit length. Therefore the running time is

$$O(LSD).$$

For Problem 55, the digit-growth bound gives \(D\le 54\), so the total work is only on the order of tens of millions of character-level operations. Space usage is \(O(D)\), since at any moment the code stores only the current decimal string, its reversal, and a small amount of loop state.

Footnotes and References

  1. Problem page: Project Euler 55 - Lychrel numbers
  2. Lychrel numbers: Wikipedia - Lychrel number
  3. Palindromic numbers: Wikipedia - Palindromic number
  4. The reverse-and-add process: Wikipedia - 196-algorithm

Problem 55 source code

C++

#include <algorithm>
#include <iostream>
#include <string>

namespace {

struct Options {
    int limit = 10000;
    int max_steps = 50;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        if (parse_int_after_prefix(arg, "--max-steps=", options.max_steps)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1 && options.max_steps >= 1;
}

bool is_palindrome(const std::string& s) {
    for (std::size_t i = 0; i < s.size() / 2U; ++i) {
        if (s[i] != s[s.size() - 1U - i]) {
            return false;
        }
    }
    return true;
}

std::string add_decimal_strings(const std::string& a, const std::string& b) {
    const std::size_t n = std::max(a.size(), b.size());
    std::string out;
    out.reserve(n + 1U);

    int carry = 0;
    for (std::size_t i = 0; i < n; ++i) {
        int sum = carry;
        if (i < a.size()) {
            sum += a[a.size() - 1U - i] - '0';
        }
        if (i < b.size()) {
            sum += b[b.size() - 1U - i] - '0';
        }
        out.push_back(static_cast<char>('0' + (sum % 10)));
        carry = sum / 10;
    }

    while (carry > 0) {
        out.push_back(static_cast<char>('0' + (carry % 10)));
        carry /= 10;
    }

    std::reverse(out.begin(), out.end());
    return out;
}

bool is_lychrel_candidate(const int n, const int max_steps) {
    std::string value = std::to_string(n);

    for (int step = 0; step < max_steps; ++step) {
        std::string rev = value;
        std::reverse(rev.begin(), rev.end());
        value = add_decimal_strings(value, rev);
        if (is_palindrome(value)) {
            return false;
        }
    }

    return true;
}

int solve(const int limit, const int max_steps) {
    int count = 0;
    for (int n = 1; n < limit; ++n) {
        if (is_lychrel_candidate(n, max_steps)) {
            ++count;
        }
    }
    return count;
}

bool run_checkpoints() {
    if (is_lychrel_candidate(47, 50)) {
        std::cerr << "Checkpoint failed for 47" << '\n';
        return false;
    }
    if (is_lychrel_candidate(349, 3)) {
        std::cerr << "Checkpoint failed for 349" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit, options.max_steps) << '\n';
    return 0;
}

Python

import sys

def parse_int_after_prefix(arg, prefix):
    if not arg.startswith(prefix):
        return False, None
    tail = arg[len(prefix):]
    if not tail:
        return False, None
    
    try:
        value = int(tail)
        if str(value) != tail:  # Check for leading zeros or invalid characters
            return False, None
        return True, value
    except ValueError:
        return False, None

def parse_arguments(args):
    options = {
        'limit': 10000,
        'max_steps': 50,
        'run_checkpoints': True
    }
    
    i = 1
    while i < len(args):
        arg = args[i]
        if arg == "--skip-checkpoints":
            options['run_checkpoints'] = False
            i += 1
            continue
        
        found, value = parse_int_after_prefix(arg, "--limit=")
        if found:
            options['limit'] = value
            i += 1
            continue
        
        found, value = parse_int_after_prefix(arg, "--max-steps=")
        if found:
            options['max_steps'] = value
            i += 1
            continue
        
        print(f"Unknown argument: {arg}", file=sys.stderr)
        return None
    
    if options['limit'] < 1 or options['max_steps'] < 1:
        return None
    
    return options

def is_palindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            return False
    return True

def add_decimal_strings(a, b):
    n = max(len(a), len(b))
    
    out = []
    carry = 0
    
    for i in range(n):
        total = carry
        if i < len(a):
            total += ord(a[len(a) - 1 - i]) - ord('0')
        if i < len(b):
            total += ord(b[len(b) - 1 - i]) - ord('0')
        
        out.append(str(total % 10))
        carry = total // 10
    
    while carry > 0:
        out.append(str(carry % 10))
        carry //= 10
    
    return ''.join(reversed(out))

def is_lychrel_candidate(n, max_steps):
    value = str(n)
    
    for step in range(max_steps):
        rev = value[::-1]
        value = add_decimal_strings(value, rev)
        if is_palindrome(value):
            return False
    
    return True

def solve(limit, max_steps):
    count = 0
    for n in range(1, limit):
        if is_lychrel_candidate(n, max_steps):
            count += 1
    return count

def run_checkpoints():
    if is_lychrel_candidate(47, 50):
        print("Checkpoint failed for 47", file=sys.stderr)
        return False
    if is_lychrel_candidate(349, 3):
        print("Checkpoint failed for 349", file=sys.stderr)
        return False
    return True

def main():
    args = sys.argv
    
    options = parse_arguments(args)
    if options is None:
        sys.exit(1)
    
    if options['run_checkpoints'] and not run_checkpoints():
        sys.exit(2)
    
    result = solve(options['limit'], options['max_steps'])
    print(result)

if __name__ == "__main__":
    main()

Java

class Euler55 {

    private static class Options {
        int limit = 10000;
        int maxSteps = 50;
        boolean runCheckpoints = true;
    }

    private static boolean parseIntAfterPrefix(String arg, String prefix, int[] valueRef) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }

        int parsed = 0;
        for (int i = 0; i < tail.length(); i++) {
            char c = tail.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }
            parsed = parsed * 10 + (c - '0');
        }
        valueRef[0] = parsed;
        return true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
                continue;
            }
            int[] ref = new int[1];
            if (parseIntAfterPrefix(arg, "--limit=", ref)) {
                options.limit = ref[0];
                continue;
            }
            if (parseIntAfterPrefix(arg, "--max-steps=", ref)) {
                options.maxSteps = ref[0];
                continue;
            }
            System.err.println("Unknown argument: " + arg);
            return false;
        }
        return options.limit >= 1 && options.maxSteps >= 1;
    }

    private static boolean isPalindrome(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    private static String addDecimalStrings(String a, String b) {
        int n = Math.max(a.length(), b.length());
        StringBuilder out = new StringBuilder(n + 1);
        int carry = 0;

        for (int i = 0; i < n; i++) {
            int sum = carry;
            if (i < a.length()) {
                sum += a.charAt(a.length() - 1 - i) - '0';
            }
            if (i < b.length()) {
                sum += b.charAt(b.length() - 1 - i) - '0';
            }
            out.append((char)('0' + (sum % 10)));
            carry = sum / 10;
        }

        while (carry > 0) {
            out.append((char)('0' + (carry % 10)));
            carry /= 10;
        }

        return out.reverse().toString();
    }

    private static boolean isLychrelCandidate(int n, int maxSteps) {
        String value = Integer.toString(n);

        for (int step = 0; step < maxSteps; step++) {
            String rev = new StringBuilder(value).reverse().toString();
            value = addDecimalStrings(value, rev);
            if (isPalindrome(value)) {
                return false;
            }
        }

        return true;
    }

    private static int solve(int limit, int maxSteps) {
        int count = 0;
        for (int n = 1; n < limit; n++) {
            if (isLychrelCandidate(n, maxSteps)) {
                count++;
            }
        }
        return count;
    }

    private static boolean runCheckpoints() {
        if (isLychrelCandidate(47, 50)) {
            System.err.println("Checkpoint failed for 47");
            return false;
        }
        if (isLychrelCandidate(349, 3)) {
            System.err.println("Checkpoint failed for 349");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }
        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }

        System.out.println(solve(options.limit, options.maxSteps));
    }
}