Detailed mathematical approach

Problem Summary

For coprime positive integers \(a\) and \(b\), let

\[ S=\langle a,b\rangle=\{ax+by:\ x,y\in\mathbb Z_{\ge 0}\} \]

be the numerical semigroup generated by \(a\) and \(b\), and let \(G(a,b)\) be the set of positive integers that do not belong to \(S\). A legal frog configuration is a subset \(A\subseteq G(a,b)\) such that for any two distinct chosen gaps, their positive difference is still outside \(S\). In the language of the title, no frog attacks another.

The implementations compute the weighted total

\[ F(a,b)=\sum_{\substack{A\subseteq G(a,b)\\ \forall\,u\ne v\in A,\ |u-v|\notin S}}\ \sum_{g\in A} g. \]

The target instance is \(F(19,53)\). The code also checks the small benchmark values \(F(3,5)=23\) and \(F(5,13)=16336\).

Mathematical Approach

The key step is to stop thinking about arbitrary integers and to replace the gap set by a finite lattice diagram. In that diagram, the attack condition becomes a clean partial order, and the final sum can be computed by a one-dimensional dynamic program.

The gaps form a staircase diagram

For a two-generator numerical semigroup with \(\gcd(a,b)=1\), every gap has a unique representation

\[ g(x,y)=ab-ax-by \]

with

\[ 1\le x\le b-1,\qquad 1\le y\le h(x),\qquad h(x)=\left\lfloor\frac{ab-1-ax}{b}\right\rfloor. \]

So the \(x\)-th column of the diagram has height \(h(x)\), and each cell \((x,y)\) corresponds to one gap value \(g(x,y)\). The positivity condition is exactly \(ax+by\lt ab\), which is why the columns taper off like a staircase. Summing the column heights gives the classical genus formula

\[ \sum_{x=1}^{b-1} h(x)=\frac{(a-1)(b-1)}2. \]

This is the finite set on which the algorithm actually works.

When do two frogs attack?

Take two cells \((x_1,y_1)\) and \((x_2,y_2)\). Their gap values satisfy

\[ g(x_1,y_1)-g(x_2,y_2)=a(x_2-x_1)+b(y_2-y_1). \]

If \(x_2\ge x_1\) and \(y_2\ge y_1\), then this difference is visibly representable by \(a\) and \(b\), so the two cells are incompatible. The important point is that the converse is also true in this bounded rectangle.

Indeed, suppose

\[ g(x_1,y_1)-g(x_2,y_2)=ap+bq \]

with \(p,q\ge 0\). Comparing coefficients gives

\[ a(x_2-x_1-p)=b(q-(y_2-y_1)). \]

Because \(-b\lt x_2-x_1\lt b\), reducing modulo \(b\) forces \(p=x_2-x_1+kb\) for some integer \(k\). If \(k\lt 0\), then \(p\lt 0\), impossible. If \(k\gt 0\), then

\[ q=(y_2-y_1)-ka\lt a-a=0, \]

again impossible since \(-a\lt y_2-y_1\lt a\). Hence \(k=0\), so \(p=x_2-x_1\) and \(q=y_2-y_1\). Therefore

\[ g(x_1,y_1)-g(x_2,y_2)\in S \iff x_2\ge x_1\ \text{and}\ y_2\ge y_1. \]

So two frogs attack exactly when their cells are comparable in the coordinatewise order. Legal frog configurations are precisely the antichains of this Ferrers poset.

Antichains become decreasing row sequences

Once the cells are read from left to right by column, an antichain has a simple description. It can use at most one cell from any fixed column, and if it chooses cells

\[ (x_1,y_1),\ (x_2,y_2),\ \dots,\ (x_k,y_k) \]

with

\[ x_1\lt x_2\lt \cdots\lt x_k, \]

then it must satisfy

\[ y_1\gt y_2\gt \cdots\gt y_k. \]

The whole two-dimensional incompatibility rule collapses to one number: after the last chosen row is \(y\), every future row must be smaller than \(y\).

Worked example: the checkpoint \(F(3,5)=23\)

For \((a,b)=(3,5)\), the column heights are

\[ h(1)=2,\qquad h(2)=1,\qquad h(3)=1,\qquad h(4)=0. \]

The cells and gap values are therefore

\[ (1,1)\mapsto 7,\qquad (1,2)\mapsto 2,\qquad (2,1)\mapsto 4,\qquad (3,1)\mapsto 1. \]

Legal nonempty antichains are

\[ \{7\},\ \{2\},\ \{4\},\ \{1\},\ \{2,4\},\ \{2,1\}. \]

For example, \(\{7,4\}\) is forbidden because \(7-4=3\in S\), while \(\{2,4\}\) is allowed because \(|4-2|=2\notin S\). The weighted total is

\[ 7+2+4+1+(2+4)+(2+1)=23, \]

matching the checkpoint. This tiny case already shows the mechanism: once row \(1\) is chosen, no later cell can be added; row \(2\) may be followed by row \(1\).

The weighted dynamic program

After some initial columns have been processed, let \(C(\ell)\) be the number of partial antichains for which the next chosen row must satisfy \(y\lt \ell\). Let \(W(\ell)\) be the total contribution

\[ \sum_{A}\sum_{g\in A} g \]

over those same partial antichains. Initially, the empty antichain is the only possibility, so

\[ C(a)=1,\qquad W(a)=0. \]

Now process one column \(x\) of height \(h(x)\).

If the column is skipped, the state \(\ell\) stays unchanged.

If one chooses the cell \((x,y)\), then \(y\) must satisfy

\[ 1\le y\le \min(h(x),\ell-1), \]

and the next state becomes \(y\). The selected gap value is \(g(x,y)=ab-ax-by\), so the transition is

\[ C_{\mathrm{new}}(y)\leftarrow C_{\mathrm{new}}(y)+C(\ell), \]

\[ W_{\mathrm{new}}(y)\leftarrow W_{\mathrm{new}}(y)+W(\ell)+C(\ell)\,g(x,y). \]

The first added term carries the previously accumulated weights. The second adds the newly selected gap once for each predecessor antichain. After the last column, the required value is

\[ F(a,b)=\sum_{\ell=1}^{a} W(\ell). \]

The correctness is now transparent: the lattice bijection identifies the gaps, the comparability test identifies attacks, and the column-by-column recurrence generates every antichain exactly once.

How the Code Works

Normalize the instance and build the diagram

The C++, Python, and Java implementations first swap the generators if necessary so that \(a\le b\). This does not change the semigroup \(\langle a,b\rangle\), the gap set, or the answer; it only makes the state space smaller. The code then iterates through the columns \(x=1,2,\dots,b-1\) and computes each column height \(h(x)\).

Maintain two one-dimensional DP tables

The main loop stores, for every possible row bound \(\ell\), how many partial antichains are currently possible and what the total selected-gap sum of those partial antichains is. For each column, a fresh copy of the current tables already accounts for the “skip this column” choice. Then every admissible row \(y\) updates the state indexed by \(y\), exactly as in the recurrence above.

The arithmetic is done with exact integers throughout. The Python and Java versions use arbitrary-precision integers automatically; the C++ version uses 128-bit unsigned arithmetic because the answer does not fit comfortably in 64 bits.

Validate with exhaustive small cases

All three implementations include a tiny brute-force checker for small coprime pairs. It explicitly lists the gap set, enumerates every subset, rejects any subset containing an attacking pair, and sums the selected gap values for the surviving subsets. This is used only on very small instances, where the number of gaps is at most 20, to confirm the optimized dynamic program. The symmetry \(F(a,b)=F(b,a)\) and the checkpoint values \(23\) and \(16336\) are also verified before the target case is computed.

Complexity Analysis

After the normalization \(a\le b\), there are \(b-1\) columns. For each column, the implementation scans \(a\) possible row bounds, and from each bound it may try up to \(a-1\) row choices. Therefore the optimized method runs in

\[ O(ba^2) \]

time and uses

\[ O(a) \]

memory. For the target pair \((19,53)\), this is tiny: only 52 columns and a state width of 19. The exhaustive checker is exponential in the number of gaps, but it is deliberately restricted to miniature instances and is not part of the final computation.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=988
2. Numerical semigroup: Wikipedia - Numerical semigroup
3. Coin problem and Frobenius theory: Wikipedia - Coin problem
4. Antichain: Wikipedia - Antichain
5. Partially ordered set: Wikipedia - Partially ordered set
6. Ferrers diagram: Wikipedia - Ferrers diagram