p714

p714.py

def genDuoDigits(d, x, y):
    #This function generates all duodigits containing the numbers x and y up to d digits
    duodigits = set()
    combs = {0}
    #We start with only the number 0
    for i in range(d):
        temp = []
        #We will now generate all i + 1 digit duodigits
        for v in combs:
            #For every existing i digit duodigit we have, we can add x or y to the end of it to create an i + 1 digit duodigit
            #We do this by multiplying it by 10 and adding x or y
            for z in [x, y]:
                t = v*10 + z
                if t != 0:
                    temp.append(t)
                    duodigits.add(t)
        #After we are done generating all i + 1 duodigits, we set combs to our list of i + 1 digit duodigits
        combs = temp
    return duodigits

def D(n):
    INF = math.inf
    d = [INF]*(n + 1)
    d[0] = 0
    
    #We create 2 sets for normal n and for "special" n, that is the n divisible by 10
    duodigits = set()
    duodigitsspecial = set()
    
    #Now we generate all our duodigits
    for x in range(0, 10):
        for y in range(x + 1, 10):
            if x == 0:
                #If x = 0, then we generate all 21 digit duodigits and this goes to the special set
                duodigitsspecial = duodigitsspecial.union(genDuoDigits(21, x, y))
            #Either case we add all normal 15 digit duodigits to the normal set
            duodigits = duodigits.union(genDuoDigits(15, x, y))
            
    #We sort both sets so that we can break out once we found the duodigit multiple (guarantees its the smallest one)
    duodigits = sorted(duodigits)
    duodigitsspecial = sorted(duodigitsspecial)
    
    for n in range(1, len(d)):
        if n % 10 == 0:
            #Special case
            for dds in duodigitsspecial:
                if dds % n == 0:
                    d[n] = dds
                    break
        else:
            #Normal case
            for dd in duodigits:
                if dd % n == 0:
                    d[n] = dd
                    break
    return sum([d[x] for x in range(len(d)) if d[x] != INF])