import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/** Project Euler Problem 1009: matching digits of n and 2n in two bases. */
public class Euler1009 {
    private static final int MAX_BASE = 20;
    private static final BigInteger TWO = BigInteger.valueOf(2);

    private static BigInteger largestValue(int a, int b) {
        if (b >= 3 * a) {
            return BigInteger.ZERO;
        }
        if (b == 2 * a) {
            return BigInteger.valueOf((long) a * (a - 1));
        }

        BigInteger baseA = BigInteger.valueOf(a);
        BigInteger baseB = BigInteger.valueOf(b);
        BigInteger maxDigit = BigInteger.valueOf(a - 1);
        List<BigInteger> weights = new ArrayList<>();
        BigInteger powerA = BigInteger.ONE;
        BigInteger powerB = BigInteger.ONE;
        BigInteger capacity = BigInteger.ZERO;

        // The first k with b^k >= 2*a^k bounds the highest digit position.
        while (powerB.compareTo(powerA.multiply(TWO)) < 0) {
            BigInteger weight = powerA.multiply(TWO).subtract(powerB);
            capacity = capacity.add(maxDigit.multiply(weight));
            weights.add(weight);
            powerA = powerA.multiply(baseA);
            powerB = powerB.multiply(baseB);
        }

        BigInteger leadingWeight = powerB.subtract(powerA.multiply(TWO));
        BigInteger value = maxDigit.min(capacity.divide(leadingWeight));
        BigInteger remaining = value.multiply(leadingWeight);

        // w_i <= 1+(a-1)*sum_(j<i) w_j makes this digitwise greedy exact.
        for (int i = weights.size() - 1; i >= 0; --i) {
            BigInteger weight = weights.get(i);
            BigInteger digit = maxDigit.min(remaining.divide(weight));
            remaining = remaining.subtract(digit.multiply(weight));
            value = value.multiply(baseA).add(digit);
        }
        return value;
    }

    private static BigInteger sumForBase(int a) {
        BigInteger result = BigInteger.ZERO;
        for (int b = a + 1; b < 3 * a; ++b) {
            result = result.add(largestValue(a, b));
        }
        return result;
    }

    private static boolean sameDigits(
            BigInteger n, BigInteger doubled, int a, int b) {
        BigInteger baseA = BigInteger.valueOf(a);
        BigInteger baseB = BigInteger.valueOf(b);
        while (n.signum() != 0 || doubled.signum() != 0) {
            BigInteger[] digitA = n.divideAndRemainder(baseA);
            BigInteger[] digitB = doubled.divideAndRemainder(baseB);
            if (!digitA[1].equals(digitB[1])) {
                return false;
            }
            n = digitA[0];
            doubled = digitB[0];
        }
        return true;
    }

    // Small exhaustive checks use long; the full computation uses BigInteger.
    private static boolean sameDigitsSmall(long n, long doubled, int a, int b) {
        while (n != 0 || doubled != 0) {
            if (n % a != doubled % b) {
                return false;
            }
            n /= a;
            doubled /= b;
        }
        return true;
    }

    private static long bruteForce(int a, int b) {
        long powerA = 1;
        long powerB = 1;
        while (powerB < 2 * powerA) {
            powerA *= a;
            powerB *= b;
        }
        long result = 0;
        for (long n = 1; n < powerA * a; ++n) {
            if (sameDigitsSmall(n, 2 * n, a, b)) {
                result = n;
            }
        }
        return result;
    }

    private static void require(boolean condition, String description) {
        if (!condition) {
            throw new IllegalStateException("Check failed: " + description);
        }
    }

    private static void runTests() {
        require(largestValue(3, 4).equals(BigInteger.valueOf(53)), "F(3,4)");
        require(largestValue(9, 10).equals(BigInteger.valueOf(8_152_650)), "F(9,10)");
        require(sumForBase(3).equals(BigInteger.valueOf(72)), "G(3)");
        for (int a = 2; a <= 7; ++a) {
            for (int b = a + 1; b <= 3 * a + 2; ++b) {
                require(
                        largestValue(a, b).equals(BigInteger.valueOf(bruteForce(a, b))),
                        "exhaustive comparison for a=" + a + ", b=" + b);
            }
        }
        for (int a = 2; a <= MAX_BASE; ++a) {
            for (int b = a + 1; b < 3 * a; ++b) {
                BigInteger value = largestValue(a, b);
                require(
                        sameDigits(value, value.multiply(TWO), a, b),
                        "matching base representations for a=" + a + ", b=" + b);
            }
        }
        System.out.println("All checks passed.");
    }

    public static void main(String[] args) {
        try {
            if (args.length == 1 && args[0].equals("--self-test")) {
                runTests();
                return;
            }
            if (args.length != 0) {
                throw new IllegalArgumentException("Usage: Euler1009 [--self-test]");
            }
            BigInteger result = BigInteger.ZERO;
            for (int a = 2; a <= MAX_BASE; ++a) {
                result = result.add(sumForBase(a));
            }
            System.out.println(result);
        } catch (RuntimeException error) {
            System.err.println(error.getMessage());
            System.exit(1);
        }
    }
}