import java.math.BigInteger;

public class BaseNImmortSearch {

	public static final int MAX_NUM = 1000000;
	public static final int MAX_BASE = 1000;

	public static String convertToAnyBase(BigInteger num, BigInteger base) {
		StringBuilder res = new StringBuilder();

		while (true) {
			BigInteger[] qr = num.divideAndRemainder(base);
			BigInteger div = qr[0];
			BigInteger mod = qr[1];

			res.insert(0, "(" + mod + ")");
			if (div.equals(BigInteger.ZERO)) {
				break;
			}

			num = div;
		}

		return res.toString();
	}

	public static boolean isImmortal(BigInteger num, BigInteger base) {
		BigInteger num2 = num.pow(2);

		String a = convertToAnyBase(num, base);
		String b = convertToAnyBase(num2, base);

		return b.endsWith(a);
	}

	public static void searchImmortals(BigInteger base) {
		for (int num = 2; num <= MAX_NUM; num++) {
			BigInteger numi = BigInteger.valueOf(num);
			if (isImmortal(numi, base)) {
				System.out.println("\t" + num + " = "
						+ convertToAnyBase(numi, base));
			}
		}
	}

	public static void main(String[] args) throws Exception {
		System.out.println("Base 2.." + MAX_BASE);
		System.out.println("Number 2.." + MAX_NUM);
		System.out.println("");

		for (int base = 2; base <= MAX_BASE; base++) {
			System.out.println("Base: " + base);
			BigInteger basei = BigInteger.valueOf(base);
			searchImmortals(basei);
		}

		System.out.println("");
		System.out.println("Fertig!");
	}

}