CODEWITHSUNDEEP
algorithmkotlinnumbersfactors
Animesh Sahu
Animesh Sahu

Reputation: 8106

How to solve divisible triangular problem (ProjectEuler) efficiently in Kotlin?

I was solving problems on the the ProjectEuler, And I am stuck on the 12th problem, the following code takes too longer not even done in five minutes and my CPU got warm.

Essentially what I am doing is generate a sequence of triangular numbers by adding successive natural numbers like:

And so on, then finding the first triangular number which has more than 500 factors (i.e. 501 factors).

fun main() {
    val numbers = generateTriangularNumbers()
    val result = numbers.first {
        val count = factorOf(it).count()
        //        println(count) // just to see the count
        count > 500
    }
    println(result)
}

// Finds factor of input [x]
private fun factorOf(x: Long): Sequence<Long> = sequence {
    var current = 1L
    while (current <= x) {
        if (x % current == 0L) yield(current++) else current++
    }
}

// generates triangular numbers, like 1, 3, 6, 10. By adding numbers like 1+2+3+...n.
private fun generateTriangularNumbers(from: Long = 1): Sequence<Long> = sequence {
    val mapper: (Long) -> Long = { (1..it).sum() }
    var current = from
    while (true) yield(mapper(current++))
}

The count (number of factors of triangular numbers) is hardly getting over 200, Is there a way to efficiently solve this problem, maybe within a minute?

Upvotes: 0

Views: 110

Answers (1)

user58697
user58697

Reputation: 7923

Project Euler is about math. Programming comes second. You need to do some homework.

  • Prove that triangular numbers are in form of n*(n+1)/2. Trivial.
  • Prove that n and n+1 are coprime. Trivial.
  • Prove, or at least convince yourself, that d(n) is multiplicative.

Combine this knowledge to come up with an efficient algorithm. You wouldn't need to actually compute the triangular numbers, and you would need to factorize the number much smaller; memoization would also avoid quite a few factorizations.

Upvotes: 2

Related Questions