First 10-digit prime in consecutive digits of e

Question

Problem. What is the first $10$-digit prime in consecutive digits of $e$.

For those of you who don't know, in 2004 the answer produced a URL to a Google employment page (sort of).
I just found about this problem in a book I was reading, I quote from that book. "The Prime Number Theorem says that among 10-digit numbers, about $1$ in $\ln10^{10}$ is a prime. This suggests that the problem isn't really so hard! Sure enough, the first 10-digit prime in consecutive digits of $e$ appears quite early."
I understand why among 10-digit numbers about $1$ in $\ln10^{10}$ is a prime. But I don't understand why this suggests that the problem is not so hard?

Answer 1

It means that a search will find the answer easily (if you have a good way to test whether a 10-digit number is prime).

For example, in Maple, this produces the answer in the blink of an eye:

> Digits:= 200;
  for n from 0 do
    esegment:= floor(10^(9+n)*exp(1)) mod 10^10;
    if isprime(esegment) then print(n, esegment); break fi
  od:

Answer 2

$\ln{10^{10}}$ is a very small number. It's roughly $23$. So that means if you only look at the first 23 10-digit numbers in the digits of $e$, you'd expect one of them to be prime.

So maybe "easy" isn't the right description, but "quick to find" (assuming you already have a way to check the prime-ness of 10-digit numbers).

Answer 3

The smallest prime can be found online with Wolfram|Alpha by using:

IsPrime[ Table[Mod[Floor[10^(n + 10) Exp[1]], 10^10], {n, 0, 100}] ]

Next to some nine digits numbers, this shows that 7 427 466 391 is the first 10- digit prime in $e$.

For more information, see this:

• MathWorld Headline News: Mathematica's Google Aptitude
• first 2 million digits of the number e

Answer 4

It has already been covered in the comments and other posts, but I thought I'd make it more explicit.

Viral campaign

A good job ad from the recruiter's perspective is one that gets many great applicants. Given the coverage this was successful. One could conjecture that a part of it is making the problem sound hard to non-applicable parties, who however will forward it to someone who they believe start enough to be able to solve it —akin to the silly puzzle books with a cartoon Einstein on the cover one gets for Christmas that are in reality easier than tensor fields. The natural log statement is interesting because it is stated as an obvious fact yet presented non-fully solved.

$$ln 10^{10} = 10 ln 10 = 23.0258509299$$

Premature Optimization Is the Root of All Evil

This problem has two requirements:

• Euler's number to a large amount of digits —computationally stored as a string as a 108+ digit integer would require a int512.
• A way to check if a number is prime

The former is available everywhere on the internet. The latter has various approaches. The "1 window in 23 is statistically a prime" part is really helpful as it is says to keep it simple as checking each 10-digit window for primality using the worst algorithm is fast as there will not be thousands o check.

I would have totally failed this as I prematurely optimised by pre-cached primes under 100,000 (square root of ten billion) using Eratosthenes sieve to test for primality of a window by checking the left over for each.

In fact in Python doing the worst primality-testing algorithm, iterating from 3 to the square root of the window until there is a left-over of zero takes 0.007 seconds to find 7427466391 at decimal position 98.

import numpy as np
import time

# get e
import requests
reply = requests.get('https://apod.nasa.gov/htmltest/gifcity/e.2mil').text
e = ''.join([line for line in [line.strip() for line in reply.split('\n')] if line and line.strip()[0].isdigit()])

tick = time.time()
    
def is_brute_prime(n:int):
    if n% 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1,2):
        if n% i == 0:
            return False
    else:
        return True
    
i = 0
se = e.replace('.','')
while True:
    frag = se[i:i+10]
    if is_brute_prime(int(frag)):
        print(frag)
        break
    i+= 1
tock = time.time()
tock - tick