It is a funny story, a comedy of errors, that started with Kepler and Galileo, and was likely picked up by Swift as a target of satire. It is assumed that Voltaire followed Swift, but it paid off for both, two Martian craters are now named after them. How ironic if the 'prediction' was indeed meant as a mockery. Another irony is that perhaps Swift should not have been so swift to mock, it is similar fitting of few data points to data that led Kepler to his famous third law, which Swift himself appears to have used. False positives are part of the process.
In January 1610 Galileo discovered the four moons of Jupiter with a newly built telescope, and informed his correspondents, including Kepler, about it. Combined with the Earth's one moon this formed a pattern, to Kepler anyway: 1,2,4..., and it meant two moons for Mars. Kepler tried geometric sequences before, for the planetary distances to the Sun, but he did not succeed even after placing extra planets between Mercury and Venus, and Mars and Jupiter. This is surprising because for the five then known planets a close fit does exist, it is now known as the Titius-Bode rule. After that Kepler turned to inscribed and circumscribed Platonic solids of Mysterium Cosmographicum (1596), another false pattern. But the story doesn't end there.
On July 25, 1610 Galileo made another discovery, and this times coded it in an anagram:
s m a i s m r m i l m e p o e t a l e u m i b u n e n u g t t a u i r a s
This looked like a challenge made just for Kepler, and he applied himself. After a while he cracked it, or so he thought:
Salue umbistineum geminatum Martia proles
(Hail, twin companionship, children of Mars).
Actually, Kepler was off by one letter, but he possibly assumed that it was a transcription error, especially since the "twin companionship" matched his earlier hunch. It wasn't. The correct unscrambling was
Altissimum planetam tergeminum observavi
(I observed the most distant planet to have a triple form),
and referred to Saturn surrounded by profiles of its rings (but Galileo did not know that at the time). When Galileo later sent another anagram Kepler pleaded: "I adjure you not to leave us long in doubt of the meaning. For you see you are dealing with real Germans. Think in what distress you place me by your silence."
Swift's Laputa was a satire of science and scientists of his time, and he couldn't do better than Kepler, with his patterns that are not always there, as a real life prototype. That he chose moons of Mars deliberately is confirmed by the fact that the orbital distances and periods he gives for them have approximately the same ratio $R^3/T^2$, as the Kepler's third law requires. Swift apparently wanted whole numbers, and noticed that $(5^3)(20^2) = 50000$ is approximately $(3^3)(43^2) = 49923$, so for his moons he chose distances of $3$ and $5$ Martian diameters with periods of $10$ and $21.5$ hours respectively (actual distances to Phobos and Deimos are 1.4 and 3.5 diameters, with periods 7.6 and 30.3 hours).
What is curious about this reconstruction is the degree of familiarity assumed of Swift with astronomy and its history (Gulliver was published in 1726), not to mention his prowess with solving Diophantine equations, I guess he did his research. But it is better than another theory, advanced by a spacecraft designer Perminov among others, that Swift found and deciphered records that Martians left on Earth.
