Problem 988: Non-attacking Frogs
View on Project EulerProject Euler Problem 988 Solution
EulerSolve provides an optimized solution for Project Euler Problem 988, Non-attacking Frogs, with C++, Python, Java, and a step-by-step mathematical explanation.
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....
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
- Problem page: https://projecteuler.net/problem=988
- Numerical semigroup: Wikipedia - Numerical semigroup
- Coin problem and Frobenius theory: Wikipedia - Coin problem
- Antichain: Wikipedia - Antichain
- Partially ordered set: Wikipedia - Partially ordered set
- Ferrers diagram: Wikipedia - Ferrers diagram
Problem 988 source code
C++
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
namespace {
using u64 = std::uint64_t;
using u128 = unsigned __int128;
u64 gcd(u64 a, u64 b) {
while (b != 0) {
const u64 r = a % b;
a = b;
b = r;
}
return a;
}
bool is_representable(const u64 n, const u64 a, const u64 b) {
for (u64 x = 0; x * a <= n; ++x) {
if ((n - x * a) % b == 0) {
return true;
}
}
return false;
}
u128 brute_force(const u64 a, const u64 b) {
std::vector<u64> gaps;
for (u64 n = 1; n < a * b; ++n) {
if (!is_representable(n, a, b)) {
gaps.push_back(n);
}
}
assert(gaps.size() <= 20);
const int n = static_cast<int>(gaps.size());
std::vector<std::vector<bool>> attack(static_cast<std::size_t>(n),
std::vector<bool>(static_cast<std::size_t>(n), false));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
const bool bad = is_representable(gaps[static_cast<std::size_t>(j)] -
gaps[static_cast<std::size_t>(i)],
a,
b);
attack[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)] = bad;
attack[static_cast<std::size_t>(j)][static_cast<std::size_t>(i)] = bad;
}
}
u128 total = 0;
const u64 full = 1ULL << n;
for (u64 mask = 0; mask < full; ++mask) {
bool ok = true;
u128 subtotal = 0;
for (int i = 0; i < n && ok; ++i) {
if (((mask >> i) & 1ULL) == 0ULL) {
continue;
}
subtotal += static_cast<u128>(gaps[static_cast<std::size_t>(i)]);
u64 rest = mask & (~0ULL << (i + 1));
while (rest != 0) {
const int j = __builtin_ctzll(rest);
if (attack[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)]) {
ok = false;
break;
}
rest &= rest - 1;
}
}
if (ok) {
total += subtotal;
}
}
return total;
}
u128 solve(u64 a, u64 b) {
if (a > b) {
std::swap(a, b);
}
const int ai = static_cast<int>(a);
const int bi = static_cast<int>(b);
const u64 ab_u64 = a * b;
const u128 ab = static_cast<u128>(ab_u64);
std::vector<u128> counts(static_cast<std::size_t>(ai + 1), 0);
std::vector<u128> sums(static_cast<std::size_t>(ai + 1), 0);
counts[static_cast<std::size_t>(ai)] = 1;
for (int x = 1; x < bi; ++x) {
const int h = static_cast<int>((ab_u64 - 1 - a * static_cast<u64>(x)) / b);
std::vector<u128> next_counts = counts;
std::vector<u128> next_sums = sums;
for (int limit = 1; limit <= ai; ++limit) {
const u128 count = counts[static_cast<std::size_t>(limit)];
if (count == 0) {
continue;
}
const u128 prefix_sum = sums[static_cast<std::size_t>(limit)];
const int ymax = std::min(h, limit - 1);
for (int y = 1; y <= ymax; ++y) {
const u128 gap = ab - static_cast<u128>(a) * static_cast<u128>(x) -
static_cast<u128>(b) * static_cast<u128>(y);
next_counts[static_cast<std::size_t>(y)] += count;
next_sums[static_cast<std::size_t>(y)] += prefix_sum + count * gap;
}
}
counts.swap(next_counts);
sums.swap(next_sums);
}
u128 answer = 0;
for (const u128 value : sums) {
answer += value;
}
return answer;
}
std::string to_string_u128(u128 value) {
if (value == 0) {
return "0";
}
std::string s;
while (value > 0) {
const int digit = static_cast<int>(value % 10);
s.push_back(static_cast<char>('0' + digit));
value /= 10;
}
std::reverse(s.begin(), s.end());
return s;
}
void run_checkpoints() {
for (u64 a = 2; a <= 7; ++a) {
for (u64 b = a + 1; b <= 8; ++b) {
if (gcd(a, b) != 1 || a * b > 35) {
continue;
}
assert(solve(a, b) == brute_force(a, b));
assert(solve(a, b) == solve(b, a));
}
}
assert(solve(3, 5) == 23);
assert(solve(5, 13) == 16336);
}
} // namespace
int main(int argc, char** argv) {
bool should_run_checkpoints = true;
for (int i = 1; i < argc; ++i) {
if (std::string(argv[i]) == "--skip-checkpoints") {
should_run_checkpoints = false;
}
}
if (should_run_checkpoints) {
run_checkpoints();
}
std::cout << to_string_u128(solve(19, 53)) << '\n';
return 0;
}
Python
import sys
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def is_representable(n, a, b):
x = 0
while x * a <= n:
if (n - x * a) % b == 0:
return True
x += 1
return False
def brute_force(a, b):
gaps = []
for n in range(1, a * b):
if not is_representable(n, a, b):
gaps.append(n)
assert len(gaps) <= 20
n = len(gaps)
attack = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
bad = is_representable(gaps[j] - gaps[i], a, b)
attack[i][j] = bad
attack[j][i] = bad
total = 0
for mask in range(1 << n):
ok = True
subtotal = 0
for i in range(n):
if ((mask >> i) & 1) == 0:
continue
subtotal += gaps[i]
rest = mask & (~0 << (i + 1))
while rest != 0:
j = (rest & -rest).bit_length() - 1
if attack[i][j]:
ok = False
break
rest &= rest - 1
if not ok:
break
if ok:
total += subtotal
return total
def solve(a, b):
if a > b:
a, b = b, a
ab = a * b
counts = [0] * (a + 1)
sums = [0] * (a + 1)
counts[a] = 1
for x in range(1, b):
h = (ab - 1 - a * x) // b
next_counts = counts[:]
next_sums = sums[:]
for limit in range(1, a + 1):
count = counts[limit]
if count == 0:
continue
prefix_sum = sums[limit]
ymax = min(h, limit - 1)
for y in range(1, ymax + 1):
gap = ab - a * x - b * y
next_counts[y] += count
next_sums[y] += prefix_sum + count * gap
counts, sums = next_counts, next_sums
return sum(sums)
def run_checkpoints():
for a in range(2, 8):
for b in range(a + 1, 9):
if gcd(a, b) != 1 or a * b > 35:
continue
assert solve(a, b) == brute_force(a, b)
assert solve(a, b) == solve(b, a)
assert solve(3, 5) == 23
assert solve(5, 13) == 16336
if __name__ == "__main__":
should_run_checkpoints = "--skip-checkpoints" not in sys.argv[1:]
if should_run_checkpoints:
run_checkpoints()
print(solve(19, 53))
Java
import java.math.BigInteger;
public class Euler988 {
private static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
private static boolean isRepresentable(long n, long a, long b) {
for (long x = 0; x * a <= n; ++x) {
if ((n - x * a) % b == 0) {
return true;
}
}
return false;
}
private static BigInteger bruteForce(long a, long b) {
long[] gaps = new long[20];
int gapCount = 0;
for (long n = 1; n < a * b; ++n) {
if (!isRepresentable(n, a, b)) {
gaps[gapCount++] = n;
}
}
if (gapCount > 20) {
throw new IllegalStateException("Too many gaps for brute force");
}
boolean[][] attack = new boolean[gapCount][gapCount];
for (int i = 0; i < gapCount; ++i) {
for (int j = i + 1; j < gapCount; ++j) {
boolean bad = isRepresentable(gaps[j] - gaps[i], a, b);
attack[i][j] = bad;
attack[j][i] = bad;
}
}
BigInteger total = BigInteger.ZERO;
long full = 1L << gapCount;
for (long mask = 0; mask < full; ++mask) {
boolean ok = true;
BigInteger subtotal = BigInteger.ZERO;
for (int i = 0; i < gapCount && ok; ++i) {
if (((mask >>> i) & 1L) == 0L) {
continue;
}
subtotal = subtotal.add(BigInteger.valueOf(gaps[i]));
long rest = mask & (~0L << (i + 1));
while (rest != 0L) {
int j = Long.numberOfTrailingZeros(rest);
if (attack[i][j]) {
ok = false;
break;
}
rest &= rest - 1;
}
}
if (ok) {
total = total.add(subtotal);
}
}
return total;
}
private static BigInteger solve(long a, long b) {
if (a > b) {
long tmp = a;
a = b;
b = tmp;
}
int ai = (int) a;
long ab = a * b;
BigInteger[] counts = new BigInteger[ai + 1];
BigInteger[] sums = new BigInteger[ai + 1];
for (int i = 0; i <= ai; ++i) {
counts[i] = BigInteger.ZERO;
sums[i] = BigInteger.ZERO;
}
counts[ai] = BigInteger.ONE;
for (int x = 1; x < b; ++x) {
int h = (int) ((ab - 1 - a * x) / b);
BigInteger[] nextCounts = counts.clone();
BigInteger[] nextSums = sums.clone();
for (int limit = 1; limit <= ai; ++limit) {
BigInteger count = counts[limit];
if (count.signum() == 0) {
continue;
}
BigInteger prefixSum = sums[limit];
int ymax = Math.min(h, limit - 1);
for (int y = 1; y <= ymax; ++y) {
long gap = ab - a * x - b * y;
nextCounts[y] = nextCounts[y].add(count);
nextSums[y] = nextSums[y].add(prefixSum.add(count.multiply(BigInteger.valueOf(gap))));
}
}
counts = nextCounts;
sums = nextSums;
}
BigInteger answer = BigInteger.ZERO;
for (BigInteger value : sums) {
answer = answer.add(value);
}
return answer;
}
private static void require(boolean condition, String message) {
if (!condition) {
throw new IllegalStateException(message);
}
}
private static void runCheckpoints() {
for (long a = 2; a <= 7; ++a) {
for (long b = a + 1; b <= 8; ++b) {
if (gcd(a, b) != 1 || a * b > 35) {
continue;
}
require(solve(a, b).equals(bruteForce(a, b)), "Brute force mismatch");
require(solve(a, b).equals(solve(b, a)), "Symmetry mismatch");
}
}
require(solve(3, 5).equals(BigInteger.valueOf(23)), "Check solve(3,5)");
require(solve(5, 13).equals(BigInteger.valueOf(16336)), "Check solve(5,13)");
}
public static void main(String[] args) {
boolean shouldRunCheckpoints = true;
for (String arg : args) {
if ("--skip-checkpoints".equals(arg)) {
shouldRunCheckpoints = false;
}
}
if (shouldRunCheckpoints) {
runCheckpoints();
}
System.out.println(solve(19, 53));
}
}