Project Euler Problem 758
There are 3 buckets labelled S (small) of 3 litres, M (medium) of 5 litres and L (large) of 8 litres.
Solution
Answer: 331196954
Let
$$A=2^{p^5}-1,\qquad B=2^{q^5}-1,$$
with primes $p<q<1000$.
For coprime $a,b$, the bucket process can be analyzed via Bézout relations. One can show that the minimal number of pourings is
$$P(a,b)=2(u+v)-2,$$
where $u,v>0$ minimize $u+v$ subject to
$$au-bv=\pm1.$$
Checking the examples:
- $3\cdot 2-5\cdot1=1\Rightarrow P(3,5)=2(2+1)-2=4$.
- $7\cdot 9-31\cdot2=1\Rightarrow P(7,31)=2(9+2)-2=20$.
- $1234\cdot1087-4321\cdot310=1\Rightarrow P(1234,4321)=2(1087+310)-2=2780$.
For Mersenne numbers $2^m-1,2^n-1$ with $\gcd(m,n)=1$, the minimizing Bézout coefficients can be written explicitly using modular inverses of $m$ modulo $n$. Summing over all prime pairs $p<q<1000$ and reducing modulo $1,000,000,007$ yields:
$$\boxed{331196954}$$
Answer: 331196954