Problem 038:

object Euler38 extends Application {
  def ispan (n :String) = n.toList.sort(_<_).mkString == "123456789";
  def catprod (n :Int, r :Int) = List.range(1, r+1).flatMap(p => (n*p).toString.toList)
  def find (n :Int, r :Int, max :Int) :Int = {
    val cp = catprod(n, r);
    if (cp.length > 9)
      if (r == 2) max
      else find(n, r-1, max);
    else
      if (ispan(cp)) find(n+1, r, Math.max(cp.mkString.toInt, max))
      else find(n+1, r, max);
  }
  println(find(1, 5, 0));
}

I wrote the above general solution which computes the concatenated product with (1, 2, 3, 4, 5) for increasing values of n until the product exceeds 9 digits, then moves down to (1, 2, 3, 4) and so on. Once I had my answer, I read the forums and discovered that a bit of thinking would have led me to the knowledge that the solution had to be a four digit value multiplied by (1, 2). Even less thinking would have made me realize that the solution had to be larger than the example given in the problem statement. Fortunately I did none of that thinking and got to write an interesting algorithm. A more thoughtful me might have written the following:

object Euler38 extends Application {
  def ispan (n :String) = n.toList.sort(_<_).mkString == "123456789";
  println(List.range(9182,9876).reverse.map(n => n+""+(2*n)).filter(ispan).head);
}

Problem 037:

object Euler37 extends EulerApp {
  val primes = genprimes(1000000);
  def isrtrunc (prime :Int) :Boolean =
    (prime == 0) || ((primes(prime) != 0) && isrtrunc(prime/10));
  def isltrunc (prime :String) :Boolean =
    prime.isEmpty || ((primes(prime.toInt) != 0) && isltrunc(prime.substring(1)));
  def istrunc (prime :Int) = isrtrunc(prime) && isltrunc(prime.toString)
  println(primes.drop(10).filter(0.!=).filter(istrunc).foldRight(0)(_+_));
}

I cheated a little and turned the integer into a string in order to easily truncate it from the left, it would perhaps have been more elegant to take the value modulo 10^digits-1 but the code would have been longer and I feel an irrational desire for brevity in these solutions.

Problem 036:

object Euler36 extends Application {
  def ispal (n :String) = n.reverse.sameElements(n)
  def bothpal (n :Int) = ispal(n.toString) && ispal(n.toBinaryString)
  println(List.range(1, 1000000, 2).filter(bothpal).foldRight(0)(_+_));
}

Brief, readable and reasonably efficient, yay for Scala. The only cleverness here is to realize that binary palindromes must be odd.

Problem 035:

object Euler35 extends EulerApp {
  val primes = genprimes(1000000);
  def digits (value :Int) :Int = if (value == 0) 0 else 1 + digits(value/10);
  def rotate (value :Int, turns :Int) :Int = {
    val mod = Math.pow(10, digits(value)-turns).intValue()
    (value % mod) * Math.pow(10, turns).intValue() + (value / mod)
  }
  def circprime (n :Int) :Boolean = {
    List.range(0, digits(n)).foldRight(true)((t, b) => (b && (primes(rotate(n, t)) != 0)))
  }
  println(primes.filter(0.!=).filter(circprime).length);
}

Coming up with rotate() was fun and the rest was pretty straightforward. I first wrote a recursive method that rotated the number one digit at a time, but then I realized I could do it in a single expression. If there existed a built in operator for raising an integer to an integer power, rotate would look much nicer.

Problem 034:

object Euler34 extends Application {
  val facts = Array(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880);
  def digfact (sum :Int, n :Int) :Int =
    if (n == 0) sum else digfact(facts(n % 10) + sum, n/10);
  def check (sum :Int, n :Int) :Int =
    if (n == 2000000) sum;
    else if (digfact(0, n) == n) check(sum+n, n+1);
    else check(sum, n+1);
  println(check(0, 10));
}

Since we’re only computing factorial for single digit numbers, we pre-compute the values of 0 through 9 factorial and then breeze up through the positive integers accumulating all numbers that meet our criterion. We stop searching at 2000000 because 1999999 is the last number for which the sum of the factorials of the digits is greater than or equal to the number itself.

Problem 033:

object Euler33 extends Application {
  def equal (ratio :Double, rnum :Int, rdenom :Int) :Boolean = {
    (rdenom > 0) && (ratio == rnum/rdenom.doubleValue());
  }
  val fracs = for {
    denom <- List.range(10,100)
    num <- List.range(10,denom)
    if ((num%10 == denom/10 && equal(num/denom.doubleValue(), num/10, denom%10)) ||
        (num/10 == denom%10 && equal(num/denom.doubleValue(), num%10, denom/10)))
  } yield Pair(num, denom);
  val prod = fracs.foldRight(Pair(1,1))((b, a) => (Pair(b._1 * a._1, b._2 * a._2)));
  println(prod._2 / prod._1);
}

Nothing too clever here. I did realize that cancellable fractions would either be kn/mk or nk/km, and fortunately the product reduces to 1/100 so determining the denominator is simple.

Problem 032:

object Euler32 extends Application {
  def digits (n :Int) = n.toString.toList.map(c => c - '0');
  def ispan (a :Int, b :Int, n :Int) :Boolean =
    (digits(a) ::: digits(n) ::: digits(b)).sort(_<_).equals(List.range(1,10));
  def haspanfact (n :Int) :Boolean =
    List.range(2, 100).find((a) => (n % a == 0 && ispan(a, n/a, n))) != None;
  println(List.range(1000, 10000).filter(haspanfact).foldRight(0)(_+_));
}

We want a factorization of a four digit number (which will be either two digits times three or one digit times four), so we enumerate all 4 digit numbers from 1000 to 9999, filter them by checking all possible one and two digit divisors first for divisibility and second for pandigitality, then sum the matches. Being able to decompose numbers into lists of digits, jam those lists together, sort them and compare them to a list with 1 through 9 in consecutive order in three lines of code sure is handy.

Problem 031:

object Euler31 extends Application {
  def perms (remain :Int, coins :List[Int]) :Int = {
    if (remain == 0) return 1;
    else if (coins == Nil) return 0;
    else List.range(0, remain/coins.head+1).map(
      q => perms(remain - q*coins.head, coins.tail)).foldRight(0)(_+_);
  }
  println(perms(200, List(200, 100, 50, 20, 10, 5, 2, 1)));
}

Nothing too fancy here, just enumerate all legal quantities of the first coin in the list (including zero), then recurse with that coin removed from the list and its value times the number chosen removed from the sum.

Problem 030:

object Euler30 extends Application {
  def digits (n :Int) = n.toString.toList.map(c => c - '0');
  def issum5 (n :Int) = digits(n).map(a => Math.pow(a, 5).intValue()).foldRight(0)(_+_) == n;
  println(List.range(2, 200000).filter(issum5).foldRight(0)(_+_));
}

A decent balance of compactness and readability, IMHO. I would like to do away with the 200,000 upper limit which I came to via some preparatory noodling.

Problem 029:

object Euler29 extends Application {
  println((for {
    a <- List.range(2, 101)
    b <- List.range(2, 101)
  } yield BigInt(a).pow(b)).removeDuplicates.length);
}

This one’s pretty easy thanks to BigInt.

Problem 028:

object Euler28 extends Application {
  def spiral (size :Int) :Int = {
    if (size == 1) return 1;
    val smaller = size-2;
    spiral(smaller) + 4*(smaller*smaller) + (1+2+3+4)*(smaller+1);
  }
  println(spiral(1001));
}

This is a slightly brevified version of my original solution which is a bit clearer:

  val smaller = size-2;
  val start = smaller*smaller;
  val step = smaller+1;
  return spiral(smaller) + ((start + 1*step) + (start + 2*step) +
                            (start + 3*step) + (start + 4*step));

Looking at the grid:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

The bold numbers are the values for start and the step is the distance from the start position to the first corner of the next ring and from that corner to the next corner.

It was a bit too Dead Poets Society at times, but the characters were likable and their circumstances not so contrived as to push one beyond the ability to suspend disbelief. I liked the portrayal of enthusiasm for learning, not so much the investigation of the morality of subjugating that passion to get into Cambridge. Fortunately the rest of the film made up for the unenjoyable main plot line.

Problem 027:

object Euler27 extends EulerApp {
  val MAX_N = 80;
  val primes = genprimes(MAX_N*MAX_N + MAX_N*1000 + 1000);
  def polyprimes (primes :Array[Int], a :Int, b :Int, n :Int) :Int =
    if (primes(Math.abs(n*n + a*n + b)) == 0) 0 else 1 + polyprimes(primes, a, b, n+1);

  val polys = for {
    a <- List.range(-1000, 1000)
    b <- List.range(-1000, 1000)
    p <- List(polyprimes(primes, a, b, 0))
    if (p > 0)
  } yield Pair(a * b, p);
  println(polys.foldLeft(Pair(0, 0))((a, b) => if (a._2 > b._2) a else b)._1);
}

Pretty straightforward. Just try all combinations from -1000 to 1000 and see how many consecutive primes are generated and pick the one that generates the most. You may notice that I’m passing the list of primes into the polyprimes function because referencing it directly from its enclosing context annoyingly results in a 40 second runtime instead of 28 seconds.

Problem 026:

object Euler26 extends Application {
  def divcycle (numer :Int, denom :Int, rlist :List[Int]) :Int = {
    val remain = numer % denom;
    if (remain == 0) return 0;
    val ridx = rlist.indexOf(remain);
    if (ridx >= 0) ridx+1 else divcycle(remain * 10, denom, remain :: rlist);
  }
  var cycles = List.range(1, 1000).map(v => divcycle(1, v, Nil));
  println(cycles.indexOf(cycles.foldRight(0)(Math.max))+1);
}

This one turned out to be easy once I realized that the key was looking at the remainder after each step in the long division process. If the remainder is ever the same as a remainder you’ve seen previously, then you’ve found a loop.

Prior to that I was tracking the actual division result and looking for loops in the digits which was problematic because one doesn’t know when to declare a repeated series of numbers a loop. I was in the middle of doing some hairbrained fiddling that involved making sure that the repeated series of digits was at least as long as all the digits that had come before it when I realized there must be a more elegant solution. Indeed there was.

Problem 025:

object Euler25 extends Application {
  var prev2 :BigInt = 1;
  var prev1 :BigInt = 1;
  var value :BigInt = prev2 + prev1;
  var term = 3;
  while (value.toString.length < 1000) {
    prev2 = prev1;
    prev1 = value;
    value = prev1 + prev2;
    term += 1;
  }
  println(term);
}

Another unglamorous solution wherein all the hard work is done by BigInt.