Monthly Archive for August, 2011

Problem 55 of Project Euler explains what Lychrel numbers are and asks one to find the number of those below 10000. The only sticking point in the whole procedure is that after a few iterations the number become so large that BigInteger needs to be used. But otherwise, just follow the wording of the statement and the problem will be solved.

Here’s the outermost loop which does the counting:

    private static final int ARRAY_SIZE = 1000000;
    private static final BigInteger BIG_ARRAY_SIZE = BigInteger.valueOf(ARRAY_SIZE);

    public static int countOfLychrelNumbers(int upperLimit) {
        int count = 0;

        State[] lychrelNumbers = ArrayUtils.createArray(ARRAY_SIZE, State.NOT_VERIFIED, new State[0]);
        for (int i = 0; i <= upperLimit; i++) {
            if (lychrelNumbers[i] == State.NON_LYCHREL) continue;
            if (lychrelNumbers[i] == State.LYCHREL || testForLychrelProperty(lychrelNumbers, i)) {
                count++;
            }
        }

        return count;
    }

    private enum State {
        LYCHREL, NON_LYCHREL, NOT_VERIFIED
    }

It’s in the testForLychrelProperty method that all the caching logic comes in. It makes sense to cache the results. However, I have imposed a cache limit as well. Here’s the messier code with caching logic:

    private static boolean testForLychrelProperty(State[] lychrelNumbers, int number) {
        int iterCount = 1;
        State state = State.NOT_VERIFIED;
        BigInteger num = BigInteger.valueOf(number);
        List<BigInteger> found = new ArrayList<BigInteger>();
        found.add(num);
        while (iterCount < 50) {
            BigInteger reverse = NumberUtil.reverse(num);
            BigInteger sum = reverse.add(num);
            if (!num.remainder(BigInteger.TEN).equals(BigInteger.ZERO)) found.add(reverse);
            state = sum.compareTo(BIG_ARRAY_SIZE) < 0 ? lychrelNumbers[sum.intValue()] : State.NOT_VERIFIED;
            if (state == State.LYCHREL || state == State.NON_LYCHREL) {
                break;
            }
            if (PalindromeUtil.checkIfPalindrome(sum.toString())) {
                state = State.NON_LYCHREL;
                break;
            }
            num = sum;
            found.add(sum);
            iterCount++;
        }

        if (state == State.NOT_VERIFIED) state = State.LYCHREL;

        setState(lychrelNumbers, found, state);
        return state == State.LYCHREL;
    }

The setState method simply updates the cache with the latest result. Here is it’s implementation:

    private static void setState(State[] lychrelNumbers, List<BigInteger> numbers, State state) {
        for (BigInteger number : numbers) {
            if (number.compareTo(BIG_ARRAY_SIZE) > 0) return;
            lychrelNumbers[number.intValue()] = state;
        }
    }

All in all, the code runs in some 180ms on my laptop.

Popularity: 6% [?]