Detailed mathematical approach

Problem Summary

Let \(f(10^K)\) denote the number of pairs \((p,q)\) with \(1 \le p \lt q \lt 10^K\) such that the decimal representations of \(p\) and \(q\) share at least one digit. For Problem 612 we need

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

A direct scan is impossible: there are \(10^{18}-1\) candidate numbers and about \(\binom{10^{18}-1}{2}\) pairs. The workable idea is to forget the exact values and remember only which decimal digits occur in each number.

Mathematical Approach

The solution counts numbers by their exact digit sets, then subtracts the pairs whose digit sets are disjoint.

Step 1: Encode Each Number by Its Digit Set

For a positive integer \(n\), let \(S(n)\subseteq\{0,1,\dots,9\}\) be the set of digits appearing in its usual decimal expansion. Two numbers are friends exactly when

$S(p)\cap S(q)\neq \varnothing.$

For each mask \(A\subseteq\{0,1,\dots,9\}\), define \(C_K(A)\) as the number of integers \(n\) with \(1\le n\lt 10^K\) and \(S(n)=A\).

Once all values \(C_K(A)\) are known, the original problem becomes a counting problem over only \(2^{10}=1024\) masks.

Step 2: Count Exact Masks with a Length DP

Let \(D_\ell(A)\) be the number of \(\ell\)-digit positive integers whose digit set is exactly \(A\). Because a decimal representation cannot start with zero, the base layer is

$D_1(\{d\})=1 \quad \text{for } d\in\{1,\dots,9\},$

and all other one-digit states are zero.

If an \(\ell\)-digit number currently uses digit set \(A\), then appending a digit \(x\in\{0,\dots,9\}\) produces an \((\ell+1)\)-digit number with digit set \(A\cup\{x\}\). So the transition is simply

$A \longrightarrow A\cup\{x\}\qquad (x=0,1,\dots,9).$

Summing over all permitted lengths gives

$C_K(A)=\sum_{\ell=1}^{K} D_\ell(A).$

This matches the range \(1\le n\lt 10^K\): every such number has between \(1\) and \(K\) digits, and leading zeros are never introduced.

Step 3: Count the Complement First

Let

$M=10^K-1.$

Then the total number of unordered pairs is

$\binom{M}{2}.$

A pair is not friendly precisely when the two digit sets are disjoint. If \(N_K\) denotes the number of unordered pairs with

$A\cap B=\varnothing,$

then the desired answer is

$f(10^K)=\binom{M}{2}-N_K.$

So the task is reduced to counting disjoint mask pairs.

Step 4: Use Subset Sums to Count Disjoint Masks Quickly

For every mask \(T\subseteq\{0,\dots,9\}\), define

$Z_K(T)=\sum_{B\subseteq T} C_K(B).$

Now fix a mask \(A\). A second number is disjoint from it exactly when its mask \(B\) is contained in the complement

$\overline{A}=\{0,1,\dots,9\}\setminus A.$

Therefore the number of choices for the second number is \(Z_K(\overline{A})\), and the number of ordered disjoint pairs is

$N_K^{\mathrm{ord}}=\sum_{A} C_K(A)\,Z_K(\overline{A}).$

The empty mask never occurs for a positive integer, so a disjoint pair can never be a self-pair. Hence every unordered disjoint pair appears exactly twice in the ordered count, which gives

$N_K=\frac{N_K^{\mathrm{ord}}}{2}.$

The values \(Z_K(T)\) are computed by the standard subset-zeta transform in \(O(10\cdot 2^{10})\) time.

Step 5: Worked Example for \(K=2\)

Now the numbers run from \(1\) to \(99\), so \(M=99\) and

$\binom{99}{2}=4851.$

The exact mask counts are easy to list:

\(\{d\}\) with \(d\in\{1,\dots,9\}\): two numbers, namely \(d\) and \(dd\).

\(\{0,d\}\): one number, namely \(d0\).

\(\{a,b\}\) with \(1\le a\lt b\le 9\): two numbers, namely \(ab\) and \(ba\).

There are no other masks below \(100\).

Now count disjoint unordered pairs by type:

$\begin{aligned} \{a\},\{b\}:&\quad \binom{9}{2}\cdot 2\cdot 2 = 144,\\ \{a\},\{0,b\},\ a\neq b:&\quad 9\cdot 8\cdot 2\cdot 1 = 144,\\ \{a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 2\cdot 2 = 1008,\\ \{0,a\},\{b,c\},\ a\notin\{b,c\}:&\quad \binom{9}{2}\cdot 7\cdot 1\cdot 2 = 504,\\ \{a,b\},\{c,d\},\ |\{a,b,c,d\}|=4:&\quad \binom{9}{4}\cdot 3\cdot 2\cdot 2 = 1512. \end{aligned}$

Therefore

$N_2=144+144+1008+504+1512=3312,$

and the number of friend pairs is

$f(10^2)=4851-3312=1539,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations keep small arrays indexed by the 1024 digit masks. One array stores the current length layer, another stores cumulative counts over all lengths up to \(K\). The process starts from the nine one-digit states, repeatedly appends each decimal digit \(0\) through \(9\), and adds every finished layer into the totals.

Next, the implementation copies the exact-mask counts into another 1024-entry array and performs ten subset-zeta passes, one pass per digit. After that transform, each mask stores the sum of all counts over its submasks, so the number of masks disjoint from a given mask can be read directly from its complement.

Finally, the implementation accumulates all ordered disjoint pairs, multiplies by the modular inverse of \(2\) to obtain unordered disjoint pairs, computes \(\binom{10^K-1}{2}\) modulo \(1000267129\), and subtracts. For the actual Project Euler input it sets \(K=18\).

Complexity Analysis

The length DP uses \(K\) layers, \(2^{10}\) masks, and \(10\) appended digits, so it costs \(O(K\cdot 10 \cdot 2^{10})\) time. The subset-zeta transform costs \(O(10\cdot 2^{10})\) time. Memory usage is \(O(2^{10})\), because only a few arrays of length \(1024\) are stored.

With decimal digits fixed, the whole method is tiny. For \(K=18\), the runtime is effectively constant relative to the enormous size of the original search space.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=612
2. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle
3. Dynamic programming: Wikipedia — Dynamic programming
4. Bit array / bitmask representation: Wikipedia — Bit array
5. Subset iteration and SOS-style preprocessing: CP-Algorithms — Enumerating submasks of a bitmask