import java.math.BigInteger;

public class ImmortBaseSchnittmenge {

	public static final int MAX_NUM = 1000000;

	/**
	 * Berechnet die Primfaktoren, aus denen sich die Zahl n zusammensetzt.
	 * Multipliziert man diese, ergibt sich die Zahl. Zurückgegeben werden die
	 * Zahlen in einem Array, das soviele Elemente hat wie n Primfaktoren. Sie
	 * sind aufsteigend sortiert.
	 * 
	 * @param n
	 *            Die zu zerlegende Zahl
	 * @return Die Primfaktoren in einem Array
	 * @see http://www.solvium.de/programmierung/java/primfaktorzerlegung/
	 */
	public static long[] primeFactors(long n) {

		/*
		 * Die Vorgehensweise ist folgende: Aufgrund der Vorgabe, dass das
		 * zurückgegebene Array maximal soviele Elemente haben darf wie die Zahl
		 * n Primfaktoren hat, erzeugen wir zunächst ein "temporäres" Array tmp,
		 * dessen Länge durch maxFactors angegeben wird. Dies geschieht aus
		 * einer Überlegung zum Speicherverbrauch: Man könnte tmp auch mit der
		 * Länge n initialisieren, allerdings ist dies aus
		 * Effizienzgesichtspunkten eher suboptimal, da jede Zahl maximal eine
		 * gewisse Anzahl an Primfaktoren haben kann. Da 2 der kleinstmögliche
		 * Primfaktor ist, ist die Anzahl der Primfaktoren immer kleiner gleich
		 * dem Exponenten der nächst- höheren Zweierpotenz. Daraus folgt: n <=
		 * 2^x log(n) <= log (2^x) x >= log (n) / log(2) Mit x als maximaler
		 * Anzahl der Primfaktoren der Zahl n.
		 */

		// Maximale Faktoranzahl ermitteln
		int maxFactors = (int) Math.ceil(Math.log10(n) / Math.log10(2));

		// Temporäres Array erzeugen
		long[] tmp = new long[maxFactors];

		// Zähler der tatsächlichen Faktoranzahl initialisieren
		int anzahlFaktoren = 0;

		/*
		 * Jetzt kommt der Trick der Zerlegung: In einer Zählschleife wird
		 * wiederholt von 2 (kleinster Primfaktor) bis n (Zahl) gezählt, wobei
		 * bei jedem Durchlauf überprüft wird, ob die Zählvariable ganzzahliger
		 * Teiler der Zahl ist. Ist dies der Fall, ist ein neuer Primfaktor
		 * gefunden. Dieser wird in tmp gesichert, und die ganze Schleife wird
		 * "zurückgesetzt", indem der Zähler erneut bei 2 (1++) beginnt und n
		 * durch n/Primfaktor ersetzt wird.
		 */
		for (long j = 2; j <= n; j++) {
			// Ist j Primfaktor?
			if (n % j == 0) {
				// Primfaktor sichern und Anzahl der Primfaktoren erhöhen
				tmp[anzahlFaktoren++] = j;
				// n ändern
				n = n / j;
				// j erneut auf Startwert 2 (1++) setzen
				j = 1;
			}
		}
		// Rückgabearray erzeugen, mit Länge der tatsächlichen Anzahl
		// von Primfaktoren
		long[] prf = new long[anzahlFaktoren];
		// Überführen der Werte des temporären Arrays in das
		// Rückgabearray
		for (int i = 0; i < anzahlFaktoren; i++) {
			prf[i] = tmp[i];
		}
		// Rückgabe
		return prf;
	}

	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);
	}

	/**
	 * Anzahl unterschiedlicher Primfaktoren
	 * 
	 * @param n
	 * @return
	 */
	public static int M(int n) {
		long[] prime = primeFactors(n);

		long last = -1;
		int count = 0;
		for (int i = 0; i < prime.length; i++) {
			long cur = prime[i];
			if (last != cur) {
				count++;
				last = cur;
			}
		}
		return count;
	}

	public static void main(String[] args) throws Exception {
		for (int num = 2; num <= MAX_NUM; num++) {
			for (int base = 2; true; base++) {
				if (M(base) == 1)
					continue;
				if (!isImmortal(BigInteger.valueOf(num), BigInteger
						.valueOf(base))) {
					System.out.println(num + " stirbt bei " + base);
					break;
				}
			}
		}
	}

}