Problem 37

Problem 37

14 February 2003

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

1. 该数最后以为只能为3, 7, 9

2. 该数的第一位可以是1-9任何数

3. 该数的中间部分只能为1, 3, 7, 9

isOk37(num)判断num是否符合条件，getNum35(mList, i)从mList中选择出所有的i位数，这个函数在Problem 35中首次出现

def isOk37(num):
    isOk = True
    if isPrime(num):
        t = num/10
        while t:
            if not isPrime(t):
                isOk = False
                break
            else:
                t = t/10
        i = 1
        while num/(10**i):
            if not isPrime(num%(10**i)):
                isOk = False
                break
            i += 1
    else:
        isOk = False
    return isOk
       

def fun37():
    pass
    count  = 0           #已经找到符合条件的数的个数
    i      = 0           #中间数的位数，从0开始
    aList  = range(1, 10)#第一位
    tList  = [3, 7, 9]   #最后一位
    mList  = [1, 3, 7, 9]#中间数
    result = 0
    while 1:
        for a in aList:
            for t in tList:
                for m in getNum35(mList, i):
                    num = int(str(a)+m+str(t))
                   
                    if isOk37(num):
                        count  += 1
                        result += num
                        if count == 11:
                            return result
        i += 1

题目说的只有11个这样的数，不知道理论在哪里
answer is 748317
time:0.280999898911
符合条件的数位23, 37, 53, 73, 313, 373, 317, 797, 3137, 3797, 3797, 739397