How were the five large solutions to the Fermat-Catalan conjecture found?

Question

The Fermat-Catalan conjecture is the statement that the equation

$a^m + b^n = c^k$

has only finitely many solutions when $a, b, c$ are positive coprime integers, and $m,n,k$ are positive integers satisfying

$\frac{1}{m} + \frac{1}{n} +\frac{1}{k} <1$. So far, ten solutions are known; five are "small" while the other five are surprisingly large. The five large ones, found by Beukers and Zagier, are:

$33^8+1549034^2=15613^3$

$1414^3+2213459^2=65^7$

$9262^3+15312283^2=113^7$

$17^7+76271^3=21063928^2$

$43^8+96222^3=30042907^2$

The earliest mention (at least the one I could find) of these solutions can be found in this paper by Henri Darmon and Andrew Granville from the mid 1990s (page 3). Richard K. Guy, in the third edition of his book Unsolved Problems in Number Theory, published in 2004, gives this quick remark;

The five big solutions were found by clever computations by Beukers and Zagier. (page 115)

Still no mention about how they were found. The "computations" would imply a computer brute-force search but seeing as how it was in the 90s, such a task would take an infeasible amount of time to finish. Looking around even further, I found a 2016 paper by Frits Beukers in which he quips:

To illustrate the phenomena we encounter when solving the generalized Fermat equation, we give a partial solution of $x^2 + y^8 = z^3$. This equation lends itself very well to a stepwise descent method. (page 3, Chapter 2)

Could that be an explanation of how the large solutions were found? I am skeptical because the paper was written more than 20 years after the large solutions were mentioned in the aforementioned Henri Darmon's and Andrew Granville's paper. Besides, the method doesn't seem to always work because later in the paper he states the following:

In many cases, like $x^3 + y^5 = z^7$, this descent is not so obvious any more... (page 4, Chapter 2)

So, how were the five large solutions found?

Update: I got hold of the second edition of Richard K. Guy's book published in 1994 and there isn't any mention of the large solutions. Thus, it is very likely that in the third edition of his book, he gets his information from the paper by Henri Darmon and Andrew Granville.

Answer 1

It would seem I grossly underestimated the computing power of the 1990s. My further research led me to Alf van der Poorten's 1996 book Notes on Fermat's last theorem. On page 146 we learn;

In preparing his problems and exercises for the Utrecht Fermatdag, Frits Beukers' tireless computer found four more solutions; Don Zagier's found a fifth. These "large" solutions are a severe blow for the respect that the "Law" of Small Numbers normally inspires.

Oh well.