2018-3-14

Find Highly Divisible Triangular Numbers with Kotlin

A solution for the Project Euler problem number 12. Written in the Java-like language Kotlin. Performance optimizations have primarily been made in the function for finding divisors.

Project Euler problem number 12 - Highly Divisible Triangular Number - is stated as follows.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The number 28 has six divisors - 1, 2, 4, 7, 14, 28.

What is the value of the first triangle number to have over five hundred divisors?

fun main(args: Array<String>) {
    // Set the target to 500 divisors.
    val target = 500

    // Create a sequence that steps 1 at the time.
    val triangleNumber = generateSequence(1, { it + 1 })
            // Get the triangle number for every number.
            .map { getTriangleNumber(it) }
            // Stop when we find a triangle number with more divisors
            // than our target.
            .first { getDivisors(it).size > target }

    // Print the answer.
    println("$triangleNumber is the first triangle number with more than $target divisors.")
}

fun getTriangleNumber(n: Int): Int {
    // Triangle numbers are given by the following formula.
    // n(n+1)/2
    return (n*(n+1)/2.0).toInt()
}

fun getDivisors(n: Int): List<Int> {
    // Factors comes in pairs, you only need to iterate to the
    // square root of n and get the paired factor using n / it.
    val limit = kotlin.math.sqrt(n.toDouble()).toInt()
    return (1..limit).filter { n % it == 0 }.flatMap {
        val squaredIsN = it * it == n
        if (squaredIsN) listOf(it) else listOf(it, n / it)
    }
}

You can run and modify the code at https://try.kotlinlang.org.

Jan Järfalk — User experienced esthete, technician, geek and web worker. Aspiring artist and recreational mathematician. I indulge and travel plenty. Constraints are good.