Algorithm of finding numbers

Question

Write a recursive algorithm which enumerates dominant primes. Your algorithm should print dominant primes as it finds them (rather than at the end).By default we limit the dominant primes we are looking for to a maximum value of 10^12, the expected run time should be around or less than a minute.

The following is my python code which doesn't work as expected:

import math
def test_prime(n):
    k = 2
    maxk = int(math.sqrt(n))
    while k <= maxk:
        if n % k == 0:
            return False
        if k == 2:
            k += 1
        else:
            k += 2
    return (n is not 1)


def dominant_prime_finder(maxprime=10**12,n=1):
    l = 1    #length of the current number
    while n // 10 > 0:
        l += 1
        n //= 10
    if test_prime(n) == True:
        is_dominant_prime = True
        index_smaller = n
        while l > 1 and index_smaller > 9:
            index_smaller //= 10
            if test_prime(index_smaller) == False:
                is_dominant_prime = False
                break
        for i in range(1,10):
            if test_prime(i*10**l + n) == True:
                is_dominant_prime = False
                break
        if is_dominant_prime == True:
            print(n)
    while n <= maxprime:
        dominant_prime_finder()

user_9027422 · Answer

You can solve the problem without enumerating all the numbers under 10^12 which is inefficient by doing a recursion on the length of the number.

It works the following way:

The prime number of length 1 are: 2,3,5,7.
For all these numbers check the third condition, for any digit dn+1∈{1,…,9} , dn+1dn…d0 is not prime. For 2 it's okay. For 3 it fails (13 for instance). Store all the prime you find in a list L. Do this for all the prime of length 1.
In L you now have all the prime number of length 2 with a prime as first digit, thus you have all the candidates for dominant prime of length 2

Doing this recursively gets you all the dominant prime, in python:

def test_prime(n):
    k = 2
    maxk = int(math.sqrt(n))
    while k <= maxk:
        if n % k == 0:
            return False
        if k == 2:
            k += 1
        else:
            k += 2
    return (n is not 1)

def check_add_digit(number,length):
    res = []
    for i in range(1,10):
        if test_prime( i*10**(length) + number ):
            res.append(i*10**(length) + number)
    return res

def one_step(list_prime,length): 
    ## Under 10^12 
    if length > 12:
        return None

    for prime in list_prime: 

        res = check_add_digit(prime,length)

        if len(res) == 0:
            #We have a dominant prime stop 
            print(prime)
        else:
            #We do not have a dominant prime but a list of candidates for length +1
            one_step(res,length+1)

one_step([2,3,5,7], length=1)

This works in under a minute on my machine.

user_10112322 · Answer

Well, there are several issues with this code:

You modify the original n at the beginning (n //= 10). This basically causes n to always be one digit. Use another variable instead: m = n while m // 10 > 0: l += 1 m //= 10
Your recursive call doesn't update n, so you enter an infinite loop: while n <= maxprime: dominant_prime_finder() Replace with: if n <= maxprime: dominant_prime_finder(maxprime, n + 1)

Even after fixing these issues, you'll cause a stack overflow simply because the dominant prime numbers are very far apart (2, 5, 3733, 59399...). So instead of using a recursive approach, use, for example, a generator:

def dominant_prime_finder(n=1):
while True:
    l = 1    #length of the current number
    m = n
    while m // 10 > 0:
        l += 1
        m //= 10
    if test_prime(n):
        is_dominant_prime = True
        index_smaller = n
        while l > 1 and index_smaller > 9:
            index_smaller //= 10
            if not test_prime(index_smaller):
                is_dominant_prime = False
                break
        for i in range(1,10):
            if test_prime(i*10**l + n):
                is_dominant_prime = False
                break
        if is_dominant_prime:
            yield n
    n = n + 1

g = dominant_prime_finder()

for i in range(1, 10):  # find first 10 dominant primes
    print(g.next())

user_2034787 · Answer

This problem is cool. Here's how we can elaborate the recurrence:

def dominant_prime_finder(maxprime=10**12):
  def f(n):
    if n > maxprime:
      return

    is_dominant = True
    power = 10**(math.floor(math.log(n, 10)) + 1)

    for d in xrange(1, 10):
      candidate = d * power + n

      if test_prime(candidate):
        f(candidate)
        is_dominant = False

    if is_dominant:
      print int(n)

  for i in [2,3,5,7]: 
    f(i)

Algorithm of finding numbers

3 Answers