What a Prime!

Number Theory Level 5

p p is a prime in the form a 1 a 2 a 3 . . . a n ‾ \overline{a_1a_2a_3...a_n} such that the integers a 1 , a 1 a 2 ‾ , a 1 a 2 a 3 ‾ , ⋯ , a 1 a 2 a 3 . . . a n ‾ a_1,\ \ \overline{a_1a_2},\ \ \overline{a_1a_2a_3},\ \cdots,\ \overline{a_1a_2a_3...a_n} are all primes.

Find the largest p . p.


The answer is 73939133.

X X by X X , 17, Taiwan

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

Jesse Nieminen
Jun 17, 2018 
 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
 
 def divisor_candidates():
        yield 2; yield 3
        i = 6
        while True:
            yield i - 1; yield i + 1
            i += 6

def is_prime(n):
    for c in divisor_candidates():
        if c * c > n:
            return True
        if n % c == 0:
            return False

def new_candidates(primes):
    for p in primes:
        for d in (1, 3, 7, 9):
            yield 10 * p + d

def main():
    primes = [2, 3, 5, 7]

    while True:
        new_primes = []
        for c in new_candidates(primes):
            if is_prime(c):
                new_primes.append(c)
        if not new_primes:
            largest = max(primes)
            break
        primes = new_primes

    print(largest)

if __name__ == "__main__":
    main()


1
 
73939133

2 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...