import java.math.BigInteger
import kotlin.math.pow

fun main() {
    println("First 10 Fermat numbers:")
    for (i in 0..9) {
        println("F[$i] = ${fermat(i)}")
    }
    println()
    println("First 12 Fermat numbers factored:")
    for (i in 0..12) {
        println("F[$i] = ${getString(getFactors(i, fermat(i)))}")
    }
}

private fun getString(factors: List<BigInteger>): String {
    return if (factors.size == 1) {
        "${factors[0]} (PRIME)"
    } else factors.map { it.toString() }
        .joinToString(" * ") {
            if (it.startsWith("-"))
                "(C" + it.replace("-", "") + ")"
            else it
        }
}

private val COMPOSITE = mutableMapOf(
    9 to "5529",
    10 to "6078",
    11 to "1037",
    12 to "5488",
    13 to "2884"
)

private fun getFactors(fermatIndex: Int, n: BigInteger): List<BigInteger> {
    var n2 = n
    val factors: MutableList<BigInteger> = ArrayList()
    var factor: BigInteger
    while (true) {
        if (n2.isProbablePrime(100)) {
            factors.add(n2)
            break
        } else {
            if (COMPOSITE.containsKey(fermatIndex)) {
                val stop = COMPOSITE[fermatIndex]
                if (n2.toString().startsWith(stop!!)) {
                    factors.add(BigInteger("-" + n2.toString().length))
                    break
                }
            }