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)

}

}

.

## 1 comment:

Too bad there's not an algebraic solution. Or if there is, I've not seen one. It seems equivalent to the factoring problem of prime numbers and thus intractible.

If there was some way to know that some values of 'n' will NEVER have some range of factors, then you could avoid a lot of duds. This would be handy like how there's the elimination rounds with the Mersenne primes site's tool.

Even better is if you could say that for example, that the value for 'n' has to be some value modulas some other value. AFAIK that's too convenient. :P

So, what are the largest numbers of factors found for a triangle number? And setting the problem to say "exactly 500" instead of over 500 is what I was assuming.

n(n+1)/2=(n^2+n)/2 heh

Post a Comment