Project Euler Problem 718
Consider the equation 17^pa+19^pb+23^pc = n where a, b, c and p are positive integers, i.e.
Solution
Answer: 228579116
Let
$$A=17^p,\qquad B=19^p,\qquad C=23^p.$$
The equation
$$Aa+Bb+Cc=n \qquad (a,b,c>0)$$
can be rewritten by setting
$$a=x+1,\quad b=y+1,\quad c=z+1 \qquad (x,y,z\ge 0),$$
giving
$$n=(A+B+C)+(Ax+By+Cz).$$
So the unreachable values for the original problem are exactly:
- all integers $<A+B+C$, and
- the shifted gaps of the numerical semigroup $\langle A,B,C\rangle$.
Thus if:
- $g$ = number of gaps of $\langle A,B,C\rangle$,
- $s$ = sum of those gaps,
- $S=A+B+C$,
then
$$G(p)=\frac{S(S-1)}2 + gS + s.$$
To compute $g$ and $s$, use the Apéry set with respect to the smallest generator $A$.
For each residue $r \pmod A$, let $w_r$ be the smallest semigroup element congruent to $r$.
These are obtained by shortest paths on residues modulo $A$, with edges:
$$r \to r+B \pmod A,\qquad r\to r+C \pmod A.$$
Then:
$$k_r=\frac{w_r-r}{A}$$
counts the gaps in that residue class, so
$$g=\sum_r k_r,$$
and
$$s=\sum_r \left(k_r r + A\frac{k_r(k_r-1)}2\right).$$
Running this for $p=6$:
$$A=17^6=24137569,$$
$$B=19^6=47045881,$$
$$C=23^6=148035889.$$
Using a radix-heap Dijkstra over the $A$ residue classes yields
$$G(6)\equiv 228579116 \pmod{1,000,000,007}.$$
Therefore:
Answer: 228579116