solving Project Euler #305

Question

Problem # 305

Let's call S the (infinite) string that is made by concatenating the consecutive positive integers (starting from 1) written down in base 10.

Thus, S = 1234567891011121314151617181920212223242...

It's easy to see that any number will show up an infinite number of times in S.

Let's call f(n) the starting position of the nth occurrence of n in S. For example, f(1)=1, f(5)=81, f(12)=271 and f(7780)=111111365.

Find Summation[f(3^k)] for 1 <= k <= 13.

How can I go about solving this?

Answer 1

My estimate of the running time is O(n² log n), so this brute force approach is not feasible.

Note that you are supposed to solve Project Euler problems yourself, which IMHO applies in particular to newer problems.