Problem 758
Buckets of Water
There are 3 buckets labelled $S$ (small) of $3$ litres, $M$ (medium) of $5$ litres and $L$ (large) of $8$ litres.
Initially $S$ and $M$ are full of water and $L$ is empty. By pouring water between the buckets exactly one litre of water can be measured.
Since there is no other way to measure, once a pouring starts it cannot stop until either the source bucket is empty or the destination bucket is full.
At least four pourings are needed to get one litre:
$$(3,5,0)\xrightarrow{M\to L} (3,0,5) \xrightarrow{S\to M} (0,3,5) \xrightarrow{L\to S}(3,3,2)
\xrightarrow{S\to M}(1,5,2)$$
After these operations, there is exactly one litre in bucket $S$.
In general the sizes of the buckets $S, M, L$ are $a$, $b$, $a + b$ litres, respectively. Initially $S$ and $M$ are full and $L$ is empty. If the above rule of pouring still applies and $a$ and $b$ are two coprime positive integers with $a\leq b$ then it is always possible to measure one litre in finitely many steps.
Let $P(a,b)$ be the minimal number of pourings needed to get one litre. Thus $P(3,5)=4$.
Also, $P(7, 31)=20$ and $P(1234, 4321)=2780$.
Find the sum of $P(2^{p^5}-1, 2^{q^5}-1)$ for all pairs of prime numbers $p,q$ such that $p < q < 1000$.
Give your answer modulo $1\ 000\ 000\ 007$.
水桶倒水
现有三个水桶，标记$S$的小水桶可以装$3$升水，标记$M$的中水桶可以装$5$升水，标记$L$的大水桶可以装$8$升水。
一开始，小水桶和中水桶均装满了水，而大水桶则是空的。通过在水桶间互相倒水，我们希望量出恰好一升水。由于我们缺乏其他的测量手段，在倒水时只能要么将倒出的水桶倒空要么将倒入的水桶装满。
为了量出恰好一升水，至少需要倒四次：
$$(3,5,0)\xrightarrow{M\to L} (3,0,5) \xrightarrow{S\to M} (0,3,5) \xrightarrow{L\to S}(3,3,2)
\xrightarrow{S\to M}(1,5,2)$$
经过这些操作后，在小水桶中恰好有一升水。
考虑一般情况，即小、中、大水桶的容积分别为$a$、$b$和$a+b$升。一开始小水桶和中水桶均装满了水而大水桶是空的。采用相同的倒水规则，若$a$和$b$是两个互质的正整数且满足$a\leq b$，那么在有限步内总是能够量出恰好一升水。
记$P(a,b)$为量出一升水所需的最少倒水次数，因此$P(3,5)=4$。
此外，$P(7, 31)=20$，$P(1234, 4321)=2780$。
对于所有满足$p < q < 1000$的素数对$p, q$，求$P(2^{p^5}-1, 2^{q^5}-1)$之和，并将你的答案对$1\ 000\ 000\ 007$取余。