Problem 156

Comments

I think I did a bad job on this problem. I made a brute force solution and then just let it run for a few hours while I watched Netflix.

The toughest part was figuring out when to stop looking. We know that the value for $s(d)$ is finite because we can estimate the total number of digits required to create numbers up to a value $10^n$. We see that this number does not grow as quickly as $n$ grows. There is a point where the number $10^n$ is larger than the digits required to create all numbers below it. It is when we reach this point that we can stop looking. Unfortunately, this number is $10^{11}$…

Code

def solve():

    n = 0
    while True:
        if 10**n < n*10**(n-1):
            break
        n += 1

    counts = {i: 0 for i in range(10)}
    total = 0
    for i in range(10**n):
        k = i
        while i:
            i, r = divmod(i, 10)
            counts[r] += 1
        total += k * tuple(counts.values()).count(k)

    return total

if __name__ == '__main__':
    print(solve())