First 10-digit prime found in consecutive digits of e

• Tweet
• Email

• Tweet
• Email

I know I’m about 16 years late on this one, but I was reading another book by Matt Parker, and he mentioned that in 2004, the following cryptic advert appeared on billboards across the USA…

It turned out that if you solved the problem and went to the site, you were faced with a much harder problem. If you solved that, then you could apply for a job at Google (which is what this was all about in the first place).

Matt Parker commented that this “would require a very creative bit of programming indeed.” Challenge accepted! Fire up LinqPad and away we go.

The first job was to get hold of the expansion of e. A quick search turned up a NASA web site that had a text file with e to 2 million places. Seemed like enough to start!

Reading these into a string variable was simple…

string e = File.ReadAllText(@"e.txt")
  .Replace("\n", "")
  .Substring(2);

We skip the first two characters, as these are “2.” which is not part of the decimal expansion.

The next job was to find a function to test a number for primality. This isn’t as hard as it sounds, given that once you knock out all multiples of 2, 3 and 5, you’ve knocked out over 62% of the candidates. Bearing in mind that a prime has to be one more or one less than a multiple of 6 allows you to short-cut the check even more, and you end up with code that can check a lot of numbers fairly quickly…

bool isPrime(long n) {
  if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {
    return false;
  }
  int limit = (int)Math.Floor(Math.Sqrt(n));
  int i = 6;
  while (i <= limit) {
    if (n % (i + 1) == 0 || n % (i + 5) == 0) {
      return false;
    }
    i += 6;
  }
  return true;
}

We first knock out all multiples of 2, 3 and 5. We could go further, but we hit the law of diminishing returns here. Next, we observe that if a number is not prime, at least one factor must be no greater than it’s square root, so we calculate the limit for our calculations, then we loop through in steps of six, checking the number above and below.

With this, it was pretty easy to come up with a Linq expression that found the first factor…

Enumerable.Range(0, e.Length - 10)
  .Select(n => new { n, s = e.Substring(n, 10) })
  .Where(n => !n.s.StartsWith("0"))
  .First(n => isPrime(Convert.ToInt64(n.s)));

The second line uses an anonymous variable, so we can keep track of where we are up to in the expansion. This wasn’t part of the original problem, but seemed easy and interesting enough to implement.

This ran so quickly that I didn’t bother timing it, and reported that the first 10-digit prime found in consecutive digits of e is 7427466391, which appears at position 99 (the code reports 98, as it’s zero-based).

Sadly, 7427466391.com is no longer available, so I can’t try the next problem!

By changing the last part of the query to use Select instead of First, I was able to find all 10-digit primes in the first two million digits of the expansion. Turns out that there are 80,692 of them, which only took a few seconds to compute.

Hmm, this “would require a very creative bit of programming indeed.” Would it? I don’t think the code above is particularly creative, nor was it hard to write. Don’t know if Matt Parker overestimated the problem, or if Linq is particularly good at expressing creative programming (which it is), but I was a bit disappointed at how easy this was to solve, and how quickly my code solved it.

Ah well, all in a day’s playing. On to the next one.