Quadratic Primes

Euler discovered the remarkable quadratic formula:

\begin{align} n^{2} + n + 41 \end{align}

It turns out that the formula will produce \(40\) primes for the consecutive integer values \(0 \leq n \leq 39\). However, when \(n = 40, 40^{2} + 40 + 41 = 40(40 + 1) + 41\) is divisible by \(41\), and certainly when \(n = 41, 41^{2} + 41 + 41\) is clearly divisible by \(41\).

The incredible formula \(n^{2} - 79n + 1601\) was discovered, which produces \(80\) primes for the consecutive values \(0 \leq n \leq 79\). The product of the coefficients, \(-79\) and \(1601\), is \(-126479\).

Considering quadratics of the form:

     \(n^2 + an + b\), where \(|a| < 1000\) and \(|b| \leq 1000\)

     e.g. \(|11| = 11\) and \(|-4| = 4\)

Find the product of the coefficients, \(a\) and \(b\), for the quadratic expression that produces the maximum number of primes for consecutive values of \(n\), starting with \(n = 0\) .

Solution

That’s a long problem description for a relatively easy task. It looks daunting, but in reality it’s quite simple.

We need to find a and b for which the consecutive values of n produce the largest amount of primes. Because the constraints are relatively low, we don’t need to optimize much, a brute-force solution will work just fine.

Oh well, maybe let’s just do one! Take a look at the formula here: \(n^2 + an + b\)

Try substituting n and think if you can spot a certain property of a or b that can limit what we need to check.

Can you see it? Hint, try: n = 0

If the n = 0, then we’re left with just b. It means that if we’re looking for consecutive values of primes, the first prime must be a number when n = 0, and in the formula there’s just b. So, b must be a prime!

import EulerHelper.naiveIsPrime

object Euler027 extends EulerApp {

  override def execute(): Int = {
    val coefficients = for {
      a <- -999 until 1000
      b <- 2 to 1000 if b.naiveIsPrime
    } yield (a, b)

    val (a, b) = coefficients.maxBy { case (a, b) =>
      consecutivePrimes(a, b)
    }

    a * b
  }

  private def consecutivePrimes(a: Int, b: Int): Int =
    Iterator.from(0).takeWhile { n =>
      (n * n + n * a + b).naiveIsPrime
    }.length

}

Final notes

The solution works relatively fast. If we had longer prime sequences, this part could’ve been a bit troublesome:

Iterator.from(0).takeWhile { n =>
  (n * n + n * a + b).naiveIsPrime
}.length

As you can see, we check .length at the very end, meaning that all the primes are collected to a list. That’s not what we need, right? To keep it clean, one could write a small helper like this one:

extension[A] (i: Iterator[A]) {
  private def countWhile(f: A => Boolean): Int = {
    var count = 0
    while (i.hasNext && f(i.next())) {
      count += 1
    }
    count
  }
}