public class A374351 { final static int TERMS_SOUGHT = 10001; final static int[] SEQ = new int[TERMS_SOUGHT]; public static void main(String[] args) { SEQ[1] = 1; SEQ[2] = 2; SEQ[3] = 3; System.out.print("1 1\n2 2\n3 3\n"); for (int term = 4; term < TERMS_SOUGHT; term++) { int jump = 1; int lpf = Math.max(largestPrimeFactorOf(SEQ[term-1]), largestPrimeFactorOf(SEQ[term-2])); for (int i = 2; i < lpf; i++) { if (!isPrime(i)) {continue;} if (SEQ[term-2] % i == 0) {continue;} if (SEQ[term-1] % i == 0) {continue;} jump *= i; } int num = 0; while (true) { num += jump; if (used(num)) {continue;} if (!isCoprime(num, SEQ[term-2])) {continue;} long product = 1; product *= (long)SEQ[term-2]; product *= (long)SEQ[term-1]; product *= (long)num; if (product < 0) { System.out.print("ERROR"); } if(!isPrimorial(calcRad(product))) {continue;} SEQ[term] = num; System.out.println("" + term + " " + num); break; } } } public static boolean used(int num) { for (int i = 1; i < TERMS_SOUGHT; i++) { if (SEQ[i] == 0) { return false; } if (SEQ[i] == num) { return true; } } return false; } public static int gcd(int num1, int num2) { if (num2 == 0) { return num1; } return gcd(num2, num1 % num2); } public static boolean isCoprime(int num1, int num2) { return gcd(num1, num2) == 1; } public static boolean isPrime(int num) { if (num <= 1) { return false; } for (int i = 2; i * i <= num; i++) { if (num % i == 0) { return false; } } return true; } public static int nextPrime(int num) { int next = num + 1; while (!isPrime(next)) { next++; } return next; } public static boolean isPrimorial(long num) { long product = 1; int prime = 2; while (product < num) { product *= prime; if (product == num) { return true; } prime = nextPrime(prime); } return false; } public static long calcRad(long num) { long rad = 1; for (long i = 2; i * i <= num; i++) { if (num % i == 0) { rad *= i; while (num % i == 0) { num /= i; } } } if (num > 1) { rad *= num; } return rad; } public static int largestPrimeFactorOf(int num) { for (int i = (int)Math.sqrt(num); i >= 2; i--) { if (!isPrime(i)) {continue;} if (num % i == 0) { return i; } } return num; } }