Digital Root

Observation 1: Digital Root is Just Mod 9 With Extra Steps

For $x \ge 1$, the digital root $d(x)$ is exactly $x \bmod 9$, except when the remainder is $0$ you write $9$ instead. Therefore $d(x) = d(y) \iff x \equiv y \pmod{9}.$

Observation 2: Billy's Test is a Congruence

Since $d(A) \equiv A \pmod{9}$ and $d(B) \equiv B \pmod{9}$, Billy's check $d(d(A)d(B)) = d(C)$ collapses to $AB \equiv C \pmod{9}.$ This is necessary for $AB = C$, but not sufficient. We need ordered triples $(A,B,C)$ with $1 \le A,B,C \le N$ such that the congruence holds but $AB \neq C$.

Observation 3: Count the Congruent Triples

Only residues modulo $9$ matter. Define $\text{freq}[r] = \bigl|\{ x \in [1,N] : x \bmod 9 = r \}\bigr|, \qquad r = 0,\dots,8.$ If $A \equiv i$ and $B \equiv j \pmod{9}$, then $AB \equiv ij \pmod{9}$. For this pair there are exactly $\text{freq}[(ij) \bmod 9]$ choices of $C$ satisfying the congruence. Grouping all pairs by residue gives $S_{\text{cong}} = \sum_{i=0}^{8} \sum_{j=0}^{8} \text{freq}[i] \cdot \text{freq}[j] \cdot \text{freq}[(ij) \bmod 9].$ That is a puny $9^3 = 729$ iterations.

Observation 4: Subtract the Exact Matches

Among those triples, the ones with $AB = C$ are not mistakes. For a fixed $A$, the admissible $B$ are those with $AB \le N$; there are $\lfloor N/A \rfloor$ of them, and $C$ is forced to be $AB$. Hence $S_{\text{eq}} = \sum_{A=1}^{N} \Bigl\lfloor \frac{N}{A} \Bigr\rfloor.$ For $N \le 10^6$ a plain $O(N)$ loop is more than fast enough.

Final Answer

$\boxed{\text{answer} = S_{\text{cong}} - S_{\text{eq}}}$

Complexity: $O(N)$ time and $O(1)$ additional memory.