Detailed mathematical approach

Problem Summary

Starting from a triple \((a,b,c)\), one move reflects exactly one coordinate:

$ (a,b,c)\to (2(b+c)-a,b,c),\quad (a,b,c)\to (a,2(c+a)-b,c),\quad (a,b,c)\to (a,b,2(a+b)-c). $

For fixed positive integers \(a\) and \(b\), the relevant positive values of \(c\) are exactly those for which

$ (a+b-c)^2-4ab $

is a perfect square. If \(T(a,b,c)\) denotes the minimum number of moves needed to make at least one coordinate equal to \(0\), then

$ F(a,b)=\sum T(a,b,c), $

where the sum runs over all such positive \(c\). The Project Euler task asks for

$ \sum_{k=1}^{18} F(2^k3^k,2^k5^k). $

A direct graph search is useful only for very small checks. The full solution replaces that search by a divisor-pair parametrization and by counting reflection steps through the Euclidean algorithm.

Mathematical Approach

Fix \(a\) and \(b\). The goal is to describe all admissible third coordinates \(c\), then evaluate the minimal distance to a zero coordinate for each of them.

Step 1: Turn the condition on \(c\) into a difference of squares

Set

$ u=\lvert a+b-c\rvert. $

The admissibility condition used by the implementations is that

$ (a+b-c)^2-4ab=s^2 $

for some integer \(s\). With \(u=\lvert a+b-c\rvert\), this becomes

$ u^2-s^2=4ab. $

So every admissible state is encoded by a factorization of \(4ab\) as a difference of two squares.

Step 2: Parametrize admissible states by factor pairs

Write

$ (u-s)(u+s)=4ab. $

Define

$ q=u-s,\qquad p=u+s. $

Then \(pq=4ab\), \(p\ge q>0\), and \(p+q=2u\) is even. Conversely, every factor pair

$ pq=4ab,\qquad p\ge q,\qquad p+q\text{ even} $

recovers

$ u=\frac{p+q}{2},\qquad s=\frac{p-q}{2}. $

This replaces the original search over \(c\) by a finite search over divisor pairs of \(4ab\).

Step 3: Each factor pair gives one or two positive values of \(c\)

Since \(u=\lvert a+b-c\rvert\), the corresponding third coordinates are

$ c_-=a+b+u,\qquad c_+=a+b-u. $

The larger branch \(c_-\) is always positive. The smaller branch \(c_+\) is admissible only when

$ a+b-u>0 \iff \frac{p+q}{2}<a+b \iff p+q<2(a+b). $

If equality holds, then \(c_+=0\), which is excluded because the sum defining \(F(a,b)\) only uses positive third coordinates.

Step 4: The move count collapses to Euclidean quotient sums

For positive integers \(x\ge y\), run the ordinary Euclidean algorithm

$ x=q_0y+r_0,\qquad y=q_1r_0+r_1,\qquad \dots,\qquad r_{m-2}=q_m r_{m-1}. $

Define the quotient sum

$ E(x,y)=q_0+q_1+\cdots+q_m. $

This is exactly the number of subtraction steps compressed by the division form of Euclid's algorithm. For a divisor pair \((p,q)\), the reflection system reduces to two possible Euclidean chains, one aiming to eliminate \(a\) and one aiming to eliminate \(b\). Their lengths are

$ E(2a,q)\qquad\text{and}\qquad E(2b,q), $

so the optimal distance for the larger branch is

$ f(p,q)=\min\bigl(E(2a,q),E(2b,q)\bigr). $

The two branches are consecutive along the same reflection chain, because reflecting the third coordinate sends

$ 2(a+b)-c_-=2(a+b)-(a+b+u)=a+b-u=c_+. $

Therefore \(c_-\) contributes \(f(p,q)\), while the smaller branch \(c_+\) contributes one less move, namely \(f(p,q)-1\), whenever \(c_+\) is positive.

Step 5: Closed formula for \(F(a,b)\)

Summing over all factor pairs gives

$ F(a,b)= \sum_{\substack{pq=4ab\\ q\le p\\ p+q\text{ even}}} \left( f(p,q)+ \begin{cases} f(p,q)-1, & p+q<2(a+b),\\ 0, & p+q\ge 2(a+b). \end{cases} \right). $

This is the exact formula evaluated by the implementations.

Step 6: Specialize to the Project Euler input family

For the actual problem,

$ a=2^k3^k,\qquad b=2^k5^k, $

so

$ 4ab=2^{2k+2}3^k5^k. $

Hence every divisor \(q\) of \(4ab\) has the form

$ q=2^{e_2}3^{e_3}5^{e_5}, \qquad 0\le e_2\le 2k+2, \qquad 0\le e_3,e_5\le k. $

That is why the implementation can enumerate all candidates by three nested loops over exponents, then recover \(p=(4ab)/q\) and apply the filters \(q\le p\) and \(p+q\) even.

Worked Example: \(F(6,10)=17\)

Take \(k=1\). Then

$ a=6,\qquad b=10,\qquad 4ab=240. $

The valid factor pairs with \(q\le p\) and \(p+q\) even are

$ (p,q)\in\{(120,2),(60,4),(40,6),(30,8),(24,10),(20,12)\}. $

Now compute the Euclidean quotient sums:

$ \begin{aligned} q=2&:& E(12,2)=6,\quad E(20,2)=10,\quad f=6,\\ q=4&:& E(12,4)=3,\quad E(20,4)=5,\quad f=3,\\ q=6&:& E(12,6)=2,\quad E(20,6)=6,\quad f=2,\\ q=8&:& E(12,8)=3,\quad E(20,8)=4,\quad f=3,\\ q=10&:& E(12,10)=6,\quad E(20,10)=2,\quad f=2,\\ q=12&:& E(12,12)=1,\quad E(20,12)=4,\quad f=1. \end{aligned} $

Here \(2(a+b)=32\), and every valid pair has \(p+q\ge 32\), so the smaller branch never contributes a positive \(c\). Therefore

$ F(6,10)=6+3+2+3+2+1=17, $

which matches the sample check used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same arithmetic plan. First they precompute the powers of \(2\), \(3\), and \(5\) needed to build \(a\), \(b\), and \(4ab\) for every \(1\le k\le 18\). For each \(k\), they enumerate all divisors \(q\) of \(4ab\) through the exponent ranges above, set \(p=(4ab)/q\), and discard pairs with \(q>p\) or odd \(p+q\).

For each surviving divisor pair they evaluate two Euclidean quotient sums, one for \((2a,q)\) and one for \((2b,q)\), keep the smaller of the two, and add the two branch contributions exactly as in the closed formula. The C++ implementation parallelizes independent values of \(k\); the Python and Java implementations perform the same computation sequentially.

Small internal checks confirm the derived formula on tiny cases and on the checkpoints

$ F(6,10)=17,\qquad F(36,100)=179. $

Complexity Analysis

For a fixed \(k\), the raw divisor enumeration uses

$ (2k+3)(k+1)^2 $

choices of \((e_2,e_3,e_5)\). Each surviving choice performs two Euclidean algorithms, and each Euclidean computation takes \(O(\log(4ab))\) division steps. So the arithmetic cost for one \(k\) is

$ O\bigl((2k+3)(k+1)^2\log(4ab)\bigr). $

If one generalizes the upper limit from \(18\) to \(K\), then the total candidate count is

$ \sum_{k=1}^{K}(2k+3)(k+1)^2=O(K^4). $

The memory usage is \(O(1)\) beyond the small power tables and loop variables.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=876
2. Euclidean algorithm: Wikipedia — Euclidean algorithm
3. Difference of two squares: Wikipedia — Difference of two squares
4. Divisor function: Wikipedia — Divisor function