Full Prime

We define a full prime as a prime number such that every suffix is also a prime.

Some examples of full primes are:

  • 2113 because all 2113, 113, 13 and 3 are all primes.
  • 6997 because all 6997, 997, 97 and 7 are all primes

Let S S be the sum of all full primes. What are the last three digits of S S ?

Clarification : 2, 3, 5 and 7 are considered as full prime.

Hint : Every suffix of a full prime is a full prime.


You might also enjoy Merge Prime .


The answer is 795.

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 17, 2016

The naive approach will be looping through all number smaller than 1 0 100 10^{100} and check if they are full primes.

We can do better. By definition, every suffix must be a prime. Hence, from the base primes 2 , 3 , 5 , 7 2,3,5,7 , we can recursively generate a list of full primes by adding a digit in front of the full primes we found. This can be done with either Depth-First Search or Breadth-First Search. My approach is using a kind of BFS with the the number of digits it possess as depth.

Surprisingly, there are no full primes with 25 digits.

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

def pow(a,d,n):
    ans = 1
    while d != 0:
        if d & 1:
            ans = (ans * a) % n
        d >>= 1
        a = (a * a) % n
    return ans

def isPrime(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:
        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

full_prime = [2,3,5,7]

ans = 0
while full_prime:    # full_prime is not empty -> continue generating full primes
    ans += sum(full_prime)

    # generate full primes by adding another a digit in front of the full primes found
    full_prime = [int(str(j)+str(i)) for i in full_prime for j in range(1,10)
                  if isPrime(int(str(j)+str(i)),100)]

print ans

This code runs in about 14 seconds.

pow(a,d,n) is built-in function. No need to write it!

Hasmik Garyaka - 3 years, 7 months ago

Log in to reply

Ah, didn't know that. Thanks for pointing that out.

Christopher Boo - 3 years, 6 months ago

https://oeis.org/search?q=2%2C3%2C5%2C7%2C13%2C17%2C23%2C37%2C43&language=english&go=Search

Hasmik Garyaka - 3 years, 7 months ago

Log in to reply

Wow, seems like OEIS has everything.

Christopher Boo - 3 years, 6 months ago

You use Miller-Rabin test, it's does not garantees prime.

Hasmik Garyaka - 3 years, 7 months ago

Log in to reply

You are right. But in this case the primes are very big. I can't think of a better primality test algorithm.

Christopher Boo - 3 years, 6 months ago

is 1000000007 a full prime? According to your question 1000000007 is also a full prime

fahim saikat - 2 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...