Charles Babbage1 (26 December 1791 – 18 October 1871) was an English mathematician, philosopher, inventor and mechanical engineer. Considered by some to be a "father of the computer", Babbage is credited with inventing the first mechanical computer that eventually led to more complex electronic designs.
After his attempt at making the first difference engine2 fell through, Babbage worked to design a more complex machine called the Analytical Engine3. It marks the transition from mechanized arithmetic to fully-fledged general purpose computation. The major innovation was that the machine was to be programmed using punched cards4: the Analytical Engine was intended to use loops of Jacquard5's punched cards to control a mechanical calculator, which could use as input the results of preceding computations. The machine was also intended to employ several features subsequently used in modern computers, including sequential control, branching and looping. It would have been the first mechanical device to be, in principle, Turing-complete6. The Analytical Engine was not a single physical machine, but rather a succession of designs that Babbage tinkered with until his death in 1871.
Ada Lovelace7 (10 December 1815 – 27 November 1852), who corresponded with Babbage during his development of the Analytical Engine, is credited with developing an algorithm that would enable the Engine to calculate a sequence of Bernoulli numbers8. For this achievement, she is often described as the first computer programmer, though no programming language had yet been invented.
Lovelace also translated and wrote literature supporting the project. Describing the engine's programming by punch cards, she wrote:
We may say most aptly that the Analytical Engine weaves algebraical patterns just as the Jacquard loom weaves flowers and leaves.
Because the machine has not been built, she has never seen her programs work. The programming language Ada10 — designed by a team led by Jean Ichbiah11 of CII Honeywell Bull12 under contract to the United States Department of Defense (DoD) from 1977 to 1983 to supersede over 450 programming languages used by the DoD at that time — was named after her. The Military Standard reference manual of the programming language was approved on December 10, 1980 (Ada Lovelace's birthday), and given the number MIL-STD-1815 in honor of Ada Lovelace's birth year.
Assignment
Looking ahead to the sorts of problems his Analytical Engine would be able to solve, Charles Babbage gave this example in a letter he wrote to Lord Bertram Bowden in 1837:
What is the smallest positive integer whose square ends in the digits 269,696?
He thought the answer might be 99,736 — whose square is 9,947,269,696 — but he wasn't so certain this was the smallest number whose square ends with 269,696.
Input
A line containing a number $$n \in \mathbb{N}_0$$, followed by a line containing a sequence of digits.
Output
The $$n$$ smallest natural numbers whose squares end with the digits given on the second line of input. For each of these natural numbers $$m$$ (in increasing order) a line of output must be generated in the format:
$$m$$ * $$m$$ = $$m^2$$
Example
Input:
5
269696Output:
25264 * 25264 = 638269696
99736 * 99736 = 9947269696
150264 * 150264 = 22579269696
224736 * 224736 = 50506269696
275264 * 275264 = 75770269696Example
Input:
3 03076
Output:
1226 * 1226 = 1503076 11274 * 11274 = 127103076 13726 * 13726 = 188403076
Epilogue
As an introduction to the video below, you should definitely have a look at the Tedx talk (Ada Lovelace: the original woman in tech13) of Zoe Philpott, the actress playing the monologue in the video.