Project Euler Problem 876
Starting with three numbers a, b, c, at each step do one of the three operations: - change a to 2(b + c) - a; - change b
Solution
Answer: 457019806569269
A key invariant of the transformation is the quadratic form
$$Q(a,b,c)=a^2+b^2+c^2-2ab-2bc-2ca.$$
Each allowed move is an involution that preserves $Q$. If one coordinate becomes zero, say $c=0$, then
$$Q(a,b,0)=(a-b)^2,$$
so a necessary condition for success is that $Q$ is a perfect square.
For fixed $a,b$, write
$$(c-a-b)^2-4ab=d^2.$$
This factors as
$$(c-a-b-d)(c-a-b+d)=4ab.$$
Let
$$x=\frac{c-a-b-d}{2},\qquad y=\frac{c-a-b+d}{2},$$
so that $xy=ab$. One can show every reachable $c$ arises from divisor pairs $x\mid a$, $y\mid b$, giving two families:
$$c=(x+y)\left(\frac{a}{x}+\frac{b}{y}\right),$$
and
$$c=(x-y)\left(\frac{a}{x}-\frac{b}{y}\right) \quad (>0).$$
The minimal number of steps $f(a,b,c)$ turns out to equal the number of subtraction steps in the subtractive Euclidean algorithm on $(x,y)$; for the second family it is one less.
For $a=6^k$, $b=10^k$, we enumerate divisors
$$x\mid 6^k,\qquad y\mid 10^k,$$
generate all candidate $c$, keep the minimal step count for duplicates, and sum.
This reproduces the checks:
$$F(6,10)=17,\qquad F(36,100)=179.$$
Carrying this out for $k=1,\dots,18$ gives
$$\sum_{k=1}^{18}F(6^k,10^k)=264180203150.$$
Answer: 264180203150