Friend Numbers

Let’s call two numbers friend numbers if their representation in base $10$ has at least one common digit. E.g. $1123$ and $3981$ are friend numbers.

Let $f(n)$ be the number of pairs $(p,q)$ with $1\le p \lt q \lt n$ such that $p$ and $q$ are friend numbers.
$f(100)=1539$.

Find $f(10^{18}) \bmod 1000267129$.

Let’s build a dynamic programming (DP) solution where the state is:

$i$ = the number of processed digits
$s$ = sum of digits
$p$ = number of non-zero digits
$z$ = smallest non-zero digit
$t$ = if we have already found a repeated digit
$u$ = if we have exceeded $N$

Let $\textbf{dp}[i][s][p][z][t][u]$ be the amount of numbers with the state defined above. Then we can have these transitions:

1. Current digit = 0

(a) If $z = 0$ and a repeated digit hasn’t been found yet, this is going to close no intervals thus $\textbf{dp}[i+1][s][p+1][z][t][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u]$, where $N_{i+1}$ is the $i+1$ th digit from the right of $N$, the number we're trying to find f(N) and $d$ is the current digit. (b) If $z = 0$ and a repeated digit has been found, then it will close $p$ intervals $\textbf{dp}[i+1][s][p+1][z][t][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times p$. (c) If $z \neq 0$, then the zero will close all intervals: $\textbf{dp}[i+1][s][p+1][0][1][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times (2^{p+1} - 1)$. 2. Current digit = $d>0$

(a) If $d \neq z$ and a repeated digit hasn’t been found yet, this will close no intervals: $\textbf{dp}[i+1][s+d][p+1][\min(d,z)][t][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u]$. (b) If $d \neq z$ and a repeated digit has been found, then it will close $p+1$ intervals: $\textbf{dp}[i+1][s+d][p+1][\min(d,z)][t][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times (p+1)$. (c) If $d = z$ and a repeated digit hasn't been found yet, then it will close $p$ intervals: $\textbf{dp}[i+1][s+d][p+1][d][1][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times p$. (d) If $d = z$ and a repeated digit has been found, then it will close $p+1$ * $2^p$ - $2^{p-1}$ intervals: If $d < s+d (\text{mod10})$: If a repeated digit hasn't been found yet: $\textbf{dp}[i+1][s+d (\text{mod10})][p+1][d][1][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times p \times 2^{p-1}$. If a repeated digit has been found: $\textbf{dp}[i+1][s+d (\text{mod10})][p+1][d][1][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times (p+1) \times 2^{p-1}$. (e) If $d = s+d (\text{mod10})$: If a repeated digit hasn't been found yet: $\textbf{dp}[i+1][s+d (\text{mod10})][p+1][d][1][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times p \times 2^p$. If a repeated digit has been found: $\textbf{dp}[i+1][s+d (\text{mod10})][p+1][d][1][u+N_{i+1} < d] += \textbf{dp}[i][s][p][z][t][u] \times (p+1) \times 2^p$. The resulting amount of friend numbers will then be $\Sigma \textbf{dp}[n][j][k][z][t][0]$, where $n$ is the amount of digits U has. The resulting pairs will be the sum of all states of the DP. As each state holds the number of friend numbers, the sum of all states is the number of friend pairs. To convert counts of numbers to pairs of numbers, each count of numbers maps to triangular number of pairs (using the formula n*(n-1)/2 where n is the count of numbers), but only half this value is taken as each pair is counted twice (once for each ordering). The answer needs to be multiplied by 2, as for each possible pair of friend numbers found, there are 2 ways to choose the one which is the left endpoint of an interval (this operation would not change the count of intervals). Lastly, this value needs to be taken modulus 1000267129 for the final result. As this is a modular arithmetic operation, it commutes with addition, so you can take the modulus of each summand individually to keep numbers small as you progress through the dynamic programming. This completes the solution, and using this approach it is possible to compute $f(10^{18}) \bmod 1000267129$. However, the actual computation of this is difficult and an actual numerical answer would require a computational program.

More Answers: