Would you count it manually? part 3

Let $a_n$ be the amount of positive integers divisible by $3$ with $n$ digits, all selected from the set $S = \left\{ {1,2,3,6,9} \right\}$ . Now suppose that $x_{n-1}$ is a positive integer with $n-1$ digits, all selected from $S$ . Depending on the remainder modulo $3$ of $x_{n-1}$ , it is possible to create a new number $x_n$ that is divisible by 3. Now:

• If $x_{n - 1} \equiv _3 1$ , then add the digit $2$ .
• If $x_{n - 1} \equiv _3 2$ , then add the digit $1$ .
• If $x_{n - 1} \equiv _3 0$ , then either add the digit $3$ , $6$ or $9$ .

It is clear that there are $5^{n-1}$ integers of the form $x_{n-1}$ , of which only $a_{n-1}$ are divisible by 3. Then: $a_n = 1 \cdot \left( {5^{n - 1} - a_{n - 1} } \right) + 3 \cdot a_{n - 1} \\ a_n = 5^{n - 1} + 2a_{n - 1}$ And, clearly: $a_1 = 3$ Expanding $a_n$ $n-1$ times: $a_n = 5^{n - 1} + 2 \cdot 5^{n - 2} + \ldots + 2^{n - 2} \cdot 5 + 2^{n - 1} \cdot a_1 \\ a_n = 5^{n - 1} + 2 \cdot 5^{n - 2} + \ldots + 2^{n - 2} \cdot 5 + 2^{n - 1} \cdot 3 \\ a_n = 2^n + \sum\limits_{k = 0}^{n - 1} {2^k \cdot 5^{n - 1 - k} } \\ a_n = 2^n + \frac{{2^n - 5^n }}{{2 - 5}} \\ a_n = \frac{{5^n + 2^{n + 1} }}{3}$ The solution of the problem is $a_{20}$ : $a_{20} = \frac{{5^{20} + 2^{21} }}{3} = \boxed{31789144579259}$

Let $S = \{1,2,3,6,9\}$ be the set of our valid digits.

We define concatenation $\sigma : { { Z } }^{ + }\times S \rightarrow { { Z } }^{ + }$ as $\quad \sigma (a,b)=10a+b$

Suppose that $x$ is a positive integer of $d$ digits and $x\equiv m \quad ({ mod } \quad 3)$ .

It's clear that $\sigma(x,a_{ i })$ is a positive integer of $d+1$ digits and $\sigma(x,a_{ i })\equiv 10m+a_{ i }\quad (mod\quad 3)$

Now let $F(d, m)$ be the amount of positive integers of $d$ digits $n_{i}$ such that $n_{ i }\equiv m \quad ({ mod } \quad 3)$

$F(1,\quad m)\quad =\quad the\quad number\quad of\quad digits\quad in\quad S\quad congruent\quad with\quad m\quad modulo\quad 3.$ $F(d,\quad m)\quad =\quad \sum _{ a\in { S } }{ F(d-1,\quad (m-a)*({10}^{-1}) mod\quad 3) }$

What this problem asks is to compute $F(20,0)$

We can compute this recursive function with Dynamic Programming approach

C++11 code

#include <iostream>
#include <vector>
#include <cstring>

std::vector<int> digits = {1,2,3,6,9};
long long DP[10][3];

int main() {
    memset(DP, 0, sizeof DP);

    DP[0][0] = 1LL;
    for (int i=0; i<=20; i++) {
        for (int j=0; j<3; j++) {
            for(auto it: digits) {
                DP[i+1][(j*10+it)%3] += DP[i][j];
            }
        }
    }

    std::cout << DP[20][0] << std::endl;

    return 0;
}

The program above prints the value of $F(20, 0)$ wich is $\boxed{31789144579259}$