import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class FermatNumbers {

    public static void main(String[] args) {
        System.out.println("First 10 Fermat numbers:");
        for ( int i = 0 ; i < 10 ; i++ ) {
            System.out.printf("F[%d] =%s\n", i, fermat(i));
        }
        System.out.printf("%nFirst 12 Fermat numbers factored:%n");
        for ( int i = 0 ; i < 13 ; i++ ) {
            System.out.printf("F[%d] =%s\n", i, getString(getFactors(i, fermat(i))));
        }
    }

    private static String getString(List<BigInteger> factors) {
        if ( factors.size() == 1 ) {
            return factors.get(0) + " (PRIME)";
        }
        return factors.stream().map(v -> v.toString()).map(v -> v.startsWith("-") ? "(C" + v.replace("-", "") + ")" : v).collect(Collectors.joining(" * "));
    }

    private static Map<Integer, String> COMPOSITE = new HashMap<>();
    static {
        COMPOSITE.put(9, "5529");
        COMPOSITE.put(10, "6078");
        COMPOSITE.put(11, "1037");
        COMPOSITE.put(12, "5488");
        COMPOSITE.put(13, "2884");
    }

    private static List<BigInteger> getFactors(int fermatIndex, BigInteger n) {
        List<BigInteger> factors = new ArrayList<>();
        BigInteger factor = BigInteger.ONE;
        while ( true ) {
            if ( n.isProbablePrime(100) ) {
                factors.add(n);
                break;
            }
            else {
                if ( COMPOSITE.containsKey(fermatIndex) ) {
                    String stop = COMPOSITE.get(fermatIndex);
                    if ( n.toString().startsWith(stop) ) {
                        factors.add(new BigInteger("-" + n.toString().length()));
                        break;
                    }
                }
                factor = pollardRhoFast(n);
                if ( factor.compareTo(BigInteger.ZERO) == 0 ) {
                    factors.add(n);
                    break;
                }
                else {
                    factors.add(factor);
                    n = n.divide(factor);
                }
            }
        }
        return factors;
    }

    private static final BigInteger TWO = BigInteger.valueOf(2);

    private static BigInteger fermat(int n) {
        return TWO.pow((int)Math.pow(2, n)).add(BigInteger.ONE);
    }