Back to index.

The problem: https://projecteuler.net/problem=40

The idea here is to find a pattern in the digits position by how many digits the number has.

First the 1 digit numbers. They range from 1 through 9 and their positions are their values. So $d_i = i$ for $1 \leq i \leq 9$. In particular, $d_1 = 1$.

For 2 digits numbers. They start at position 10. They all have 2 digits so they occupy two "slots" each. At positions 10 and 11 we have the digits for 10; at positions 12 and 13, we have the digits for 11 and so forth and so on. The 2 digits numbers range from 10 to 99 and a formula for their position is the following. The starting position for a two digit-number $n$ is $10 + 2(n-10)$. It's minimum is 10 and its maximum is $10 + 2(99-10) = 188$. We know now that $d_{10} = 1$ and $d_{100} = 5$ because $n = 55$ gives $10 + 2(n-10) = 100$ (so, the stating position for $n=55$ is 100).

For 3 digits numbers. We know the starting position of 99 is 188. So the starting position for 100 is $188+2=190$. Each 3-digit number occupies three slots and thus we arrive at a similar formula. For a 3-digit number $n$, it starting position is $190 + 3(n-100)$. This ranges from 190 up to $190 + 3(999-100) = 2887$. This will certainly give us $d_{1000}$. We want to find $n$ such that $190 + 3(n-100)$ is 1000 or close. If we solve for 1000, we find 370, so $d_{1000}$ is actually 3 (because we have just found that 370 starts at position 1000).

For 4-digits numbers, we know the starting position of 999 is $190 + 3(999-100) = 2887$ and, thus, the starting position for 1000 is digit position $2887+3 = 2890$. In a similar way, given $n$ a 4-digit number, it's starting position will be $2890 + 4(n-1000)$, which ranges from 2890 to 38886. This will help us find $d_{10000}$.

The procedure now is clear enough that we could write an algorithm for it. Instead of doing this tedius formula derivation by hand, we'll write a python program to follow this procedere we've been following.

ds = []
next_i_to_find = 1
range_from = 1
num_digits = 1
while next_i_to_find <= 10**6:
    smallest_num_digits_num = 10**(num_digits-1)
    largest_num_digits_num = smallest_num_digits_num*10 - 1
    range_to = range_from + num_digits*(largest_num_digits_num - smallest_num_digits_num)
    while next_i_to_find >= range_from and next_i_to_find < range_to+num_digits:
        n = ((next_i_to_find - range_from)//num_digits) + smallest_num_digits_num
        starting_pos_of_n = range_from + num_digits*(n - smallest_num_digits_num)
        assert starting_pos_of_n <= next_i_to_find
        digits_of_n = []
        while n > 0:
            digits_of_n.append(n%10)
            n //= 10
        digits_of_n.reverse()
        ds.append(digits_of_n[next_i_to_find - starting_pos_of_n])
        next_i_to_find *= 10
    range_from = range_to+num_digits
    num_digits += 1

print(ds)
p = 1
for d in ds:
    p *= d
print(p)

[1, 1, 5, 3, 7, 2, 1]
210

The code is messy, but it captures what we were doing by hand in the starting text.