Detailed mathematical approach

Problem Summary

Call a positive integer heptaphobic if it is not divisible by 7 and it still stays non-divisible by 7 after every valid swap of two decimal digits. Swaps that would move 0 to the front are ignored, because they would not produce another number of the same length. The goal is to count all heptaphobic numbers below \(10^{13}\).

A direct test of every integer is hopeless. The implementations instead count numbers by length, fix the nonzero residue \(m=n\bmod 7\), and ask which digit patterns make it impossible for any admissible swap to force the residue to \(0\).

Mathematical Approach

Take a length-\(L\) number with digits \(d_0,d_1,\dots,d_{L-1}\):

$n=\sum_{i=0}^{L-1} d_i\,10^{L-1-i}.$

Modulo 7, only the positional weights matter, so define

$w_i\equiv 10^{L-1-i}\pmod 7.$

Then \(n\bmod 7\) is simply \(\sum d_iw_i\bmod 7\). The whole method comes from understanding how a swap changes this residue and from compressing positions with the same weight.

Residue Change Under a Digit Swap

If digits at positions \(i\) and \(j\) are exchanged, every other term is unchanged, so the residue changes by

$\Delta\equiv d_jw_i+d_iw_j-d_iw_i-d_jw_j\equiv (d_j-d_i)(w_i-w_j)\pmod 7.$

Therefore a number with residue \(m\in\{1,\dots,6\}\) becomes divisible by 7 after that swap exactly when

$m+(d_j-d_i)(w_i-w_j)\equiv 0\pmod 7.$

This already shows why the code never needs the full decimal values of the digits. Only their residues modulo 7 matter.

Six Positional Weight Classes

Because \(10\equiv 3\pmod 7\) and \(10^6\equiv 1\pmod 7\), the powers of 10 repeat modulo 7 with period 6:

$10^k\bmod 7\in\{1,3,2,6,4,5\},\qquad 10^{k+6}\equiv 10^k\pmod 7.$

So, for a fixed length \(L\), every non-leading position belongs to one of six weight classes. All positions in the same class have the same multiplier \(w_i\), and swapping two digits inside one class does nothing modulo 7 because then \(w_i-w_j\equiv 0\pmod 7\).

That means a whole class can be summarized by four facts:

the set of residues that occur there, the set of nonzero residues that occur there, the sum of the class digits modulo 7, and the number of ordered digit tuples that realize that same summary.

This compression is exactly what the problem needs. Pairwise swap safety depends only on which residues appear in each class, while the overall residue of the number depends only on the weighted class sums.

Forbidden Swaps Become Shifted Residue Intersections

Take two different weight classes with weights \(a\) and \(b\), and suppose the whole number has residue \(m\). If one class contains a digit residue \(r\) and the other contains a residue \(s\), the swap between those positions is forbidden precisely when

$m+(s-r)(a-b)\equiv 0\pmod 7.$

Since \(a\not\equiv b\pmod 7\), the difference \(a-b\) has an inverse modulo 7. Define

$t(a,b,m)\equiv -m(a-b)^{-1}\pmod 7.$

Then the forbidden relation becomes

$s\equiv r+t(a,b,m)\pmod 7.$

So two class summaries are compatible exactly when the residue set of the first class, shifted by \(t(a,b,m)\), is disjoint from the residue set of the second class. That is the key simplification used by the implementations: every swap condition turns into a tiny 7-bit set-intersection test.

A concrete example helps. If \(m=5\), \(a=3\), and \(b=1\), then \(a-b\equiv 2\), its inverse is \(4\), and

$t(3,1,5)\equiv -5\cdot 4\equiv 1\pmod 7.$

So any residue \(r\) appearing in the weight-3 class forbids the residue \(r+1\pmod 7\) in the weight-1 class.

The Leading Digit Has a Special Constraint

Swaps involving the first digit are asymmetric, because a later 0 cannot be moved to the front. Such a swap would create a leading zero and is excluded by the problem statement. For that reason the leading digit is handled separately, chosen from the residues of the digits \(1,\dots,9\), and compared with the other classes using only the nonzero residues present there.

There is also one important no-op case. If the leading weight reappears later in the number, then swapping with that position cannot change the residue at all, because the two weights are equal modulo 7. Since the original residue \(m\) is already nonzero, such swaps can never create a multiple of 7.

The Global Condition Becomes a Small Search

Fix the length \(L\), the target residue \(m\in\{1,\dots,6\}\), and the leading-digit residue \(r_0\). If the first position has weight \(w_0\), the remaining weight classes must contribute

$\sum_C w(C)\,\sigma(C)\equiv m-r_0w_0\pmod 7,$

where \(\sigma(C)\) is the stored digit-sum residue for class \(C\).

So the problem is now finite and discrete: choose one summary for each active weight class, keep every pair of chosen summaries compatible, and make the weighted sum land on the required residue. The implementations solve this with a depth-first search that always branches on the class with the fewest remaining summaries, which gives strong pruning.

Worked Example: Two-Digit Numbers

For \(L=2\), the weights are \(3\) and \(1\), so a number \(10a+b\) has residue

$m\equiv 3a+b\pmod 7.$

The only possible digit swap produces \(10b+a\), and the residue change is

$\Delta\equiv (b-a)(3-1)\equiv 2(b-a)\pmod 7.$

Take \(12\). Its residue is \(3\cdot 1+2\equiv 5\pmod 7\), but swapping gives \(21\equiv 0\pmod 7\), so \(12\) is not heptaphobic. By contrast, \(13\equiv 6\pmod 7\) and its swap \(31\equiv 3\pmod 7\), so that swap does not violate the rule. The full algorithm uses exactly this modular test, but it applies it class by class instead of number by number.

How the Code Works

Precomputed Residue Summaries

The C++, Python, and Java implementations first precompute three small constant tables: the six-term cycle of \(10^k\bmod 7\), the number of possible leading digits for each residue class, and the catalogue of summary types for a weight class of a given size. Each summary type records which residues appear, which nonzero residues appear, what the class contributes to the digit sum modulo 7, and how many ordered digit assignments produce that same summary.

For the actual bound \(10^{13}\), every non-leading weight class has size 0, 1, or 2, so these catalogues stay tiny: there is 1 summary of size 0, 8 summaries of size 1, and 35 summaries of size 2.

Counting One \((L,m)\) Instance

For a fixed length \(L\) and target residue \(m\), the implementation counts how many non-leading positions belong to each of the six weights. Every active class receives its list of possible summaries together with its weighted modular contribution. It also precomputes, for every ordered pair of distinct weight classes, which summaries can coexist without creating a forbidden swap.

Next, the leading-digit residue is chosen. That immediately removes any class summaries that would allow a forbidden nonzero swap with the front position. After that, a recursive search picks one summary for one class at a time, intersects the remaining candidate sets with the precomputed compatibility tables, updates the running residue sum, and multiplies by the number of concrete digit assignments represented by each chosen summary.

Building the Final Count

The result is summed over all nonzero residues \(m=1,\dots,6\) for a fixed length, and then over all lengths from 1 through 13. Small built-in checks on short ranges verify the logic before the final count below \(10^{13}\) is produced.

Complexity Analysis

A brute-force approach would inspect almost \(10^{13}\) integers and, for each one, consider up to \(\binom{13}{2}\) digit swaps. The implemented method never iterates over concrete numbers at that scale.

For each pair \((L,m)\) with \(1\le L\le 13\) and \(m\in\{1,\dots,6\}\), there are at most six non-leading weight classes. Each class uses only a small precomputed summary catalogue, and for this bound no class has more than 35 relevant summaries. The search depth is therefore at most six, with heavy pruning from pairwise compatibility and the modular sum condition. Memory usage is \(O(1)\) relative to the numeric bound, because only small residue tables and candidate masks are stored.

In practice the running time is dominated by a modest branch-and-prune search across the \((L,m)\) cases, which is why the method is fast enough even though direct enumeration would be completely infeasible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=954
2. Modular arithmetic: Wikipedia - Modular arithmetic
3. Multiplicative order: Wikipedia - Multiplicative order
4. Positional notation: Wikipedia - Positional notation
5. Backtracking: Wikipedia - Backtracking