Pi And Googol Prime

Computer Science Level 3

Let S S be the sum of all 100-digit prime numbers found in consecutive digits of π \pi to the 100,000 decimal places. What is the digit sum of S S ?

Clarification : The numbers should not have leading zeroes. 00857 is considered as a 3-digit number.

The image is of the Google Billboard Puzzle in 2004 asking for the first 10-digit prime number found in consecutive digits of e e . It's been more than 10 years since the puzzle being published in Silicon Valley, and over 800 Brilliant.org users have solved the problem ! Now, computers have more computational power and programmers are getting smarter and younger, which inspired this problem.


The answer is 447.

Christopher Boo by Christopher Boo , 24, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Christopher Boo
Jun 16, 2016

Here is a file of π \pi to a million digit. From there, we just remove the first 2 characters 3. and we have the string of digits we wanted! 

 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
 
from random import randint

def pow(a,d,n):
    ans = 1
    while d != 0:
        if d & 1:    # is odd
            ans = (ans * a) % n
        d = d / 2
        a = (a * a) % n
    return ans

def is_prime(n, k):
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0: return False

    s = 0
    d = n-1
    while d & 1 == 0:    # is even
        s += 1
        d >>= 1

    for i in range(k):
        a = randint(2, n-2)    # 2 <= a <= n-2
        x = pow(a,d,n)
        if x == 1: continue
        for j in range(s):
            if x == n-1: break
            x = (x * x) % n
        else:
            return False
    return True

s = raw_input()

length = 100
ans = 0

i = 0
while i + length < 100000:
    x = int(s[i:i+length])
    if len(str(x)) == length and is_prime(x,100):
        ans += x
        print x
    i += 1

ans = sum([int(c) for c in str(ans)])
print ans

3 Helpful 0 Interesting 0 Brilliant 0 Confused

Your solution implies that we know that digits of π \pi to the 100,000 digits beforehand. Isn't it better to figure out all these digits on your own? Or shouldn't you mention in your problem statement that you know the 100,0000 digits right from the start?

Pi Han Goh - 4 years, 12 months ago

Log in to reply

But it's not exactly hard to find these on the web, even if you can't just ask Mathematica for the digits, which is what I did.

Mark Hennings - 4 years, 11 months ago

Log in to reply

Thanks for your response!

Pi Han Goh - 4 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...