A gritty, gut punch of a film. I couldn’t completely wrap my head around Plainview Senior but his performance was top-notch.

Problem 045:

object Euler45 extends Application {
  def findh (pent :Long, h :Long) :Long = {
    val hex = h*(2*h-1)
    if (hex > pent) findh(pent, h-1)
    else if (hex < pent) 0
    else hex
  }
  def findp (tri :Long, p :Long) :Long = {
    val pent = p*(3*p-1)/2
    if (pent > tri) findp(tri, p-1)
    else if (pent < tri) 0
    else findh(pent, p-1)
  }
  def find (t :Long) :Long = {
    val n = findp(t*(t+1)/2, t-1)
    if (n != 0) n
    else find(t+1)
  }
  println(find(286))
}

We know that for a given t, any number p for which pent(p) = tri(t) will be less than t. The same holds for hex and pent. So we search down from our starting n for a matching pentagonal number and if we find it, we search further down for a matching hexagonal number. We also know that when we get to an n that generates a pent that is less than our tri we can stop because pent(n) will only keep getting smaller and thus never be equal to our tri.

findp() and findh() are similar enough that they could be abstracted into something like:

  def findf (n :Long, x :Long, funcs :List[(Long => Long)]) :Long = {
    val fx = funcs.head(x)
    if (fx > n) findf(n, x-1, funcs)
    else if (fx < n) 0
    else if (funcs.size == 1) fx
    else findf(fx, x-1, funcs.tail)
  }

but that’s just crazy. (It also turns out to be quite a bit slower.)

Problem 044:

object Euler44 extends Application {
  def pent (n :Int) = n*(3*n-1)/2
  val pents = Set() ++ List.range(1, 3000).map(pent)
  def find (a :Int, b :Int) :Int = {
    val pa = pent(a)
    val pb = pent(b)
    val d = pb-pa
    val s = pa+pb
    if (pents.contains(d) && pents.contains(s)) d
    else if (a >= b) find(1, b+1)
    else find(a+1, b)
  }
  println(find(1, 2))
}

This one’s not especially elegant or clever (but it is fast). We just scanning increasing pairs of integers for a pair that meets our criteria and stop when we find it. We optimize by generating a “sufficiently large” list of pentagonal numbers and putting them in a set so that we can quickly test a sum or difference for pentagonality.

Went to see a performance of Verdi’s Requiem last night at the Roman Theater in Orange. We arrived just as the show was starting and had to do battle at the ticket office and again at the gate to actually get in, but the trouble was worth it as the (unfortunately blurry) picture shows:

Problem 043:

object Euler43 extends Application {
  def compsum (n :Long, digits :List[Int], divs :List[Int], sum :Long) :Long = {
    if (digits.isEmpty) n + sum
    else (for { d <- digits; val nn = n*10 + d; if ((nn%1000) % divs.head == 0) }
          yield compsum(nn, digits-d, divs.tail, sum)).foldLeft(0L)(_+_)
  }
  def digits (n :Int) = n.toString.toList.map(_-'0')
  def norepeats (n :Int) = digits(n).removeDuplicates == digits(n)
  def compute (s :Int) =
    compsum(s, 0.to(9).toList -- digits(s), List(2, 3, 5, 7, 11, 13, 17), 0)
  println(100.to(999).filter(norepeats).map(compute).reduceLeft(_+_))
}

I first tackled this one by generating all permutations of the digits zero through nine and checking to see whether they met the divisibility requirements, but that took a bit too long. Then I switched to this approach which builds up the solutions one digit at a time, pruning all values that don’t preserve our requirements. We start with all three digit numbers that don’t have repeating digits (I cheat a bit here and ignore any less than 100 as those are tricker to compute and the solution contains none of them), then we tack on each of the remaining digits in turn and make sure the trailing three digits are divisible by two. Then we move on to the next digit, and so on. This runs substantially faster (460ms as opposed to 120000ms) but the code is a bit harder to follow.

The Tour de France happened to be passing about 5km from where I’m staying (near Les Baux des Provence), so naturally a viewing was in order. The first group came and went in the span of about two seconds:

Then maybe half a minute later the second, much larger, group whizzed by. They were a bit more spread out, turning to single file after this short red clump at the head:

Zoom zip! We could feel the whoosh of the giant wind tunnel as we stood on the side of the road.