Problem 43(Sub-string divisibility)

Problem 43(Sub-string divisibility)

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let \(d_{1}\) be the 1st digit, \(d_{2}\) be the 2nd digit, and so on. In this way, we note the following:

 

• \(d_{2}d_{3}d_{4}=406\) is divisible by 2
• \(d_{3}d_{4}d_{5}=063\) is divisible by 3
• \(d_{4}d_{5}d_{6}=635\) is divisible by 5
• \(d_{5}d_{6}d_{7}=357\) is divisible by 7
• \(d_{6}d_{7}d_{8}=572\) is divisible by 11
• \(d_{7}d_{8}d_{9}=728\) is divisible by 13
• \(d_{8}d_{9}d_{10}=289\) is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

 

In Python:

import time
import math

def isprime(n):
    if n == 0 or n == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return False
        return True

def swap(s, i, j):
    nList = list(s)
    nList[j], nList[i] = nList[i], nList[j]
    return ''.join(nList)

def undersort(s, i):
    nList = list(s)
    nList = nList[0: i] + sorted(nList[i:])
    return ''.join(nList)

def lexico(nStr):
    lenStr = len(nStr)
    for i in range(lenStr - 2, -1, -1):
        for j in range(lenStr - 1, i, -1):
            if int(nStr[i]) < int(nStr[j]):
                nStr = swap(nStr, i, j)
                nStr = undersort(nStr, i + 1)
                return nStr


startTime = time.time()
nStr = '0123456789'
lenPanList = math.factorial(len(nStr))
primeSet = [2, 3, 5, 7, 11, 13, 17]
panList = [123456789]
check = 0
total = 0
for i in range(1, lenPanList):
    nStr = lexico(nStr)
    panList.append(int(nStr))
for data in panList:
    check = 0
    for i in range(0, 7):
        if int(str(data)[i + 1: i + 4]) % primeSet[i] != 0:
            check = 1
            break
    if check == 0:
        total += data
print(total)
print(time.time() - startTime, "seconds")

Run time: 25.070194244384766 seconds

 

Solution: 16695334890