This is a solution to project Euler problem 12: "What is the value of the first triangle number to have over five hundred divisors?"
This is actually a fairly easy problem to solve, providing you use a sufficiently efficient function to count the divisors!
The method I've adopted for this is particularly simple, but performs sufficiently well to solve this problem as stated within a few seconds.
Triangle Numbers:
Just a quick refresher, the triangle numbers are the sum of integers from 1 to n.
An Arithmetic series is a number series of the form:
a + (a + b) + (a + 2b) + ....
and using this form the Triangle numbers can be written as:
1 + (1 + 1) + (1 + 2) + (1 + 3) + ...
so they clearly are of the form of an Arithmetic series.
The more interesting aspect of this problem was the generation of the Triangle number sequence. Naturally, wanting to use Scala to solve this problem, the idea of using a Stream to evaluate the triangle number sequence lazily on demand is a natural approach.
The implementation I settled on to produce the Stream of triangle numbers was the iterative version as follows:
val trianglesI = Stream.iterate((1L,0L)){
case (n, sum) => (n + 1L, sum + n) }.map(_._2)
Which is a fairly natural way to solve via the additive definition of the triangle numbers.
What's perhaps more interesting is finding some alternative ways to achieve the same thing, here are some alternatives to the iterative additive stream definition:
Using the multiplicative definition of the Triangle numbers and the map function:
// use a stream map and the multiplicative solution for triangle numbers
val trianglesM = Stream.from(1).map(n => n * (n + 1) / 2)
println("trianglesM take(5)")
trianglesM.take(5).foreach(println)
Using "inits" - inits are a concept that can be found in languages such as Haskell:
// using inits (not efficient)
// inits -> inits(Stream.from(1)) is Stream(Stream(), Stream(1), Stream(1, 2), Stream(1, 2, 3), ...)
// and tails -> tails(Stream(1)) = Stream(Stream(1,2,3,...), Stream(2,3,4,...), Stream(3,4,5,...), ...)
def inits[T](xs: Stream[T]) = Stream.from(0).map(xs.take(_))
val trianglesInits = inits(Stream.from(1)).tail.map(_.sum)
println("trianglesInits take(5)")
trianglesInits.take(5).foreach(println)
Using Stream.cons and a helper function zipWith that can zip tuples:
// using zipWith
def zipWith[T1,T2,T3](s1: Stream[T1], s2: Stream[T2])(fn: (T1,T2) => T3) =
s1.zip(s2).map(Function.tupled(fn))
lazy val trianglesZ: Stream[Int] = Stream.cons(1, zipWith(trianglesZ,
Stream.from(2))(_ + _))
println("trianglesZ take(5)")
trianglesZ.take(5).foreach(println)
So, whilst problem 12 is not too hard, the production of triangle numbers as lazy lists is quite interesting, being that there are several approaches that can be taken!
The whole program solution to problem 12 (and the alternative triangle number streams)
package projecteuler
object Problem12 {
def main(args : Array[String]) {
println("result = " + problem12(500))
}
def problem12(target : Int) {
// using Stream.iterate to create a lazy stream of triangle numbers
val trianglesI = Stream.iterate((1L,0L)){
case (n, sum) => (n + 1L, sum + n) }.map(_._2)
// test it
//println("trianglesI take(5)")
//trianglesI.take(5).foreach(println)
// count the divisors (not massively efficient, but sufficient)
def numDivisors(n : Long) = {
var count = 0
for (i <- 1L to Math.sqrt(n).toInt) {
if (n % i == 0) {
count = count + 2
}
}
count
}
trianglesI.find(p => numDivisors(p) > target)
}
def otherTriangleStreams {
// use a stream map and the multiplicative solution for triangle numbers
val trianglesM = Stream.from(1).map(n => n * (n + 1) / 2)
println("trianglesM take(5)")
trianglesM.take(5).foreach(println)
// using inits (not efficient)
// inits -> inits(Stream.from(1)) is Stream(Stream(), Stream(1), Stream(1, 2), Stream(1, 2, 3), ...)
// tails -> tails(Stream(1)) = Stream(Stream(1,2,3,...), Stream(2,3,4,...), Stream(3,4,5,...), ...)
def inits[T](xs: Stream[T]) = Stream.from(0).map(xs.take(_))
val trianglesInits = inits(Stream.from(1)).tail.map(_.sum)
println("trianglesInits take(5)")
trianglesInits.take(5).foreach(println)
// using zipWith
def zipWith[T1,T2,T3](s1: Stream[T1], s2: Stream[T2])(fn: (T1,T2) => T3) = s1.zip(s2).map(Function.tupled(fn))
lazy val trianglesZ: Stream[Int] = Stream.cons(1, zipWith(trianglesZ, Stream.from(2))(_ + _))
println("trianglesZ take(5)")
trianglesZ.take(5).foreach(println)
}
}
.
Posts
