Detailed mathematical approach

Problem Summary

Let \(a=17^p\), \(b=19^p\), and \(c=23^p\). The task is to compute the sum of all positive integers that cannot be written in the form

$n=ax+by+cz,\qquad x,y,z\in \mathbb{Z}_{>0},$

for the target case \(p=6\), with the final result reduced modulo \(10^9+7\). Since \(a\), \(b\), and \(c\) are pairwise coprime, there are only finitely many unreachable integers, so the problem becomes a finite numerical-semigroup calculation rather than an infinite search.

Mathematical Approach

The solution converts the positive-coefficient representation problem into a statement about gaps of a numerical semigroup. Those gaps are then recovered from the Apéry set with respect to the smallest generator.

Step 1: Shift from positive coefficients to a semigroup

Define the numerical semigroup

$S=\langle a,b,c\rangle=\{ia+jb+kc:i,j,k\in \mathbb{Z}_{\ge 0}\}.$

Also let

$s=a+b+c.$

If \(x,y,z\ge 1\), then

$ax+by+cz=s+\bigl(a(x-1)+b(y-1)+c(z-1)\bigr).$

So a positive integer \(n\) is representable with all three coefficients positive exactly when

$n-s\in S.$

This means the unreachable positive integers consist of two parts:

$1,2,\dots,s-1,$

and all integers of the form

$s+g,$

where \(g\) is a gap of \(S\), meaning \(g\notin S\).

If \(g(S)\) denotes the number of gaps of \(S\), and \(\sigma(S)\) denotes the sum of those gaps, then the required quantity is

$U(p)=\frac{s(s-1)}{2}+s\,g(S)+\sigma(S).$

Step 2: Use residues modulo the smallest generator

Because \(a=17^p\) is the smallest generator, working modulo \(a\) gives the smallest state space. For each residue \(r\in\{0,1,\dots,a-1\}\), define

$w_r=\min\{m\in S:m\equiv r\pmod a\}.$

The set \(\{w_0,\dots,w_{a-1}\}\) is the Apéry set of \(S\) with respect to \(a\). Once \(w_r\) is known, every reachable number in residue class \(r\) is

$w_r,\ w_r+a,\ w_r+2a,\dots,$

and every smaller nonnegative number in the same residue class is unreachable.

Step 3: Compute the Apéry set by shortest paths

Construct a directed graph on the residue classes modulo \(a\). From residue \(u\), add two edges

$u\to u+b\pmod a,\qquad u\to u+c\pmod a.$

The two edge weights are \(b\) and \(c\), respectively.

Any path from \(0\) to residue \(r\) represents a value \(jb+kc\) with that residue, and its path length is exactly that value. Therefore the shortest-path distance from \(0\) to \(r\) is the smallest semigroup element in that residue class.

No separate edge for \(+a\) is needed. Adding \(a\) does not change the residue and only increases the total value, so it can never improve a minimal representative. Hence Dijkstra's algorithm returns precisely the values \(w_r\).

Step 4: Recover the number of gaps

Write each Apéry element as

$w_r=r+a q_r,\qquad q_r\in \mathbb{Z}_{\ge 0}.$

Then the gaps in residue class \(r\) are

$r,\ r+a,\ r+2a,\dots,r+(q_r-1)a,$

so that residue class contributes exactly \(q_r\) gaps. Summing over all residue classes gives

$g(S)=\sum_{r=0}^{a-1} q_r=\frac{1}{a}\sum_{r=0}^{a-1} w_r-\frac{a-1}{2}.$

If we define

$W_1=\sum_{r=0}^{a-1} w_r,$

then

$g(S)=\frac{W_1}{a}-\frac{a-1}{2}.$

Step 5: Recover the sum of the gaps

The gaps in one residue class form an arithmetic progression, so their sum is

$q_r r+\frac{a q_r(q_r-1)}{2}.$

Substituting \(q_r=(w_r-r)/a\) and simplifying yields the standard Apéry identity

$\sigma(S)=\frac{1}{2a}\sum_{r=0}^{a-1} w_r^2-\frac12\sum_{r=0}^{a-1} w_r+\frac{a^2-1}{12}.$

With

$W_2=\sum_{r=0}^{a-1} w_r^2,$

this becomes

$\sigma(S)=\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}.$

Step 6: Final formula

Combining the shift argument with the two Apéry identities gives

$\boxed{U(p)=\frac{s(s-1)}{2}+s\left(\frac{W_1}{a}-\frac{a-1}{2}\right)+\left(\frac{W_2}{2a}-\frac{W_1}{2}+\frac{a^2-1}{12}\right).}$

This is exactly the quantity evaluated modulo \(10^9+7\) by the implementations.

Worked Example: \(p=1\)

For \(p=1\), we have \(a=17\), \(b=19\), \(c=23\), and \(s=59\). The full Apéry set modulo \(17\) is

$\left(w_0,\dots,w_{16}\right)=\left(0,69,19,88,38,107,23,92,42,111,61,130,46,115,65,134,84\right).$

Therefore

$W_1=1224,\qquad W_2=114036.$

The number of gaps of \(S\) is

$g(S)=\frac{1224}{17}-\frac{16}{2}=72-8=64,$

and the sum of the gaps is

$\sigma(S)=\frac{114036}{34}-\frac{1224}{2}+\frac{17^2-1}{12}=3354-612+24=2766.$

Hence

$U(1)=\frac{59\cdot 58}{2}+59\cdot 64+2766=1711+3776+2766=8253,$

which matches the small checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. They first compute the three powers \(17^p\), \(19^p\), and \(23^p\), choose the smallest one as the modulus, and run Dijkstra's algorithm on the residue graph from Step 3.

The resulting distance table is the Apéry set. The implementation then accumulates the two moment sums \(W_1=\sum w_r\) and \(W_2=\sum w_r^2\), reducing everything modulo \(10^9+7\).

The formulas for \(g(S)\), \(\sigma(S)\), and \(U(p)\) contain division by \(2\), \(12\), and \(a\). Since the modulus is prime and coprime to those values, the code performs those divisions by modular inverses.

The same logic reproduces the checkpoints \(U(1)=8253\) and \(U(2)=60258000\) before evaluating the target case \(p=6\).

Complexity Analysis

The residue graph has \(a=17^p\) vertices and exactly two outgoing edges from each vertex. With a binary heap, Dijkstra's algorithm runs in \(O(a\log a)\) time and uses \(O(a)\) memory. The post-processing pass that forms \(W_1\) and \(W_2\) is linear, so the total complexity remains \(O(a\log a)\) time and \(O(a)\) space.

Footnotes and References

1. Problem page: Project Euler 718
2. Numerical semigroup: Wikipedia - Numerical semigroup
3. Frobenius coin problem: Wikipedia - Frobenius coin problem
4. Dijkstra's algorithm: Wikipedia - Dijkstra's algorithm
5. Modular multiplicative inverse: Wikipedia - Modular multiplicative inverse