projecteuler.net

3-Like Numbers

Published on Sunday, 15th March 2020, 07:00 am; Solved by 243

Problem 706

For a positive integer $n$, define $f(n)$ to be the number of non-empty substrings of $n$ that are divisible by 3. For example, the string "2573" has 10 non-empty substrings, three of which represent numbers that are divisible by 3, namely 57, 573 and 3. So $f(2573) = 3$.

If $f(n)$ is divisible by 3 then we say that $n$ is 3-like.

Define $F(d)$ to be how many $d$ digit numbers are 3-like. For example, $F(2) = 30$ and $F(6) = 290898$.

Find $F(10^5)$. Give your answer modulo $1\,000\,000\,007$.