Google, Euler's Number and the Hidden Prime

I used continued fractions. We first change $e$ into its continued fraction representation:

$\large{e=[2;1,2,1,1,4,1,1,6,1,1,8,…]}.$

We can find the $100th$ convergent fraction approximation of $e:$

$e \approx \frac{3652840521386397770775930229533596171296167783910904555909}{5085525453460186301777867529962655859538011626631066055111}$

This approximation turns out to be sufficient for finding the required prime.

Due to time limitations, we cannot use conventional methods to check if a ten digit number is prime or not, therefore I used the Miller-Rabin primality test to quickly check for primality.

Here is the final code in python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

from decimal import *
import random
getcontext().prec = 1000

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n == 1 or n % 2 == 0:
        return False
    elif n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n < _smallprimeset:
        return n in smallprimeset


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

a , b , n  = 0 , 1 , 100
while n:
    if n%3==2:
        m=(n+1)/3*2
    else:
        m=1
    a, b, n = b, a+m*b, n-1

e = str( Decimal(a) / Decimal(b) )
n = 1
while True:
    n += 1
    Number = e[ n : n + 10]
    if isprime( int(Number) ):
        print Number
        break

One can program it with other languages too but it is done pretty straightforward with Mathematica.

FromDigits[#] & /@ 
  Partition[RealDigits[E - 2, 10, 1000] // First, 10, 1];

Select[%, PrimeQ] // First

The first line of the code selects all strings of length 10 from the first 1000 consecutive digits of e. Much Like this: {7182818284, 1828182845, 8281828459, 2818284590 ... }.

The second line of the code Selects the elements of the list which are primes and returns the First one.

When run, the code returns:

$\boxed{7427466391}$

By the way, if you do not believe that Google really did this: Please read this

Solution Courtsey: @bobbym none

By the way, the problem is inspired by this discussion.

An easy way to do it in Mathematica without the need to convert digits to strings and then back:

Select[Table[Floor[Mod[E*10^(10+n), 10^10]], {n, 0, 100}], PrimeQ]

If you multiply e by 10^10 then take its residue of modulo 10^10, you get the first ten digits after the decimal place as an integer. Repeat by multiplying by successively larger multiples of 10 until the prime is discovered.

Java solution -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public static void main(String args[]) throws IOException{
        String e = read();
        for(int n = 0;;n++)
            if(prime(Double.parseDouble(e.substring(n, n + 10)))){
                System.out.println(e.substring(n, n + 10));
                break;
            }
    }

static boolean prime(double n){
        if(n == 2) return true;
        if(n % 2 == 0) return false;
        for(double i = 3; i * i <= n; i += 2)
            if(n % i == 0) return false;
        return true;
    }

Execution time ~ 0.003239731 seconds (without time taken to read the e file)

Method to read e -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

static String read() throws IOException{
        String e = null;
        try(BufferedReader br = new BufferedReader(new FileReader("e.txt"))) {
            StringBuilder sb = new StringBuilder();
            String line = br.readLine();
            while (line != null) {
                sb.append(line);
                sb.append(System.lineSeparator());
                line = br.readLine();
            }
            e = sb.toString();
        }
        return e.replaceAll("\\s+","");
    }