

Charles Babbage, looking ahead to the sorts of problems his Analytical Engine would be able to solve, gave this example:

 What is the smallest positive integer whose square ends in the digits 269,696?

— Babbage, letter to Lord Bowden, 1837; see Hollingdale and Tootill, Electronic Computers, second edition, 1970, p. 125.

He thought the answer might be 99,736, whose square is 9,947,269,696; but he couldn't be certain.



Task[edit]
The task is to find out if Babbage had the right answer — and to do so, as far as your language allows it, in code that Babbage himself would have been able to read and understand.
As Babbage evidently solved the task with pencil and paper, a similar efficient solution is preferred.

For these purposes, Charles Babbage may be taken to be an intelligent person, familiar with mathematics and with the idea of a computer; he has written the first drafts of simple computer programmes in tabular form. [Babbage Archive Series L].



Motivation
The aim of the task is to write a program that is sufficiently clear and well-documented for such a person to be able to read it and be confident that it does indeed solve the specified problem.




-- The program is written in the programming language Ada. The name "Ada" 
-- has been chosen in honour of your friend, 
--      Augusta Ada King-Noel, Countess of Lovelace (née Byron). 
--
-- This is an program to search for the smallest integer X, such that
-- (X*X) mod 1_000_000 = 269_696.
--
-- In the Ada language, "*" represents the multiplication symbol, "mod" the 
-- modulo reduction, and the underscore "_" after every third digit in 
-- literals is supposed to simplify reading numbers for humans. 
-- Everything written after "--" in a line is a comment for the human, 
-- and will be ignored by the computer. 
 
with Ada.Text_IO; 
-- We need this to tell the computer how it will later output its result. 
 
procedure Babbage_Problem is
 
   -- We know that 99_736*99_736 is 9_947_269_696. This implies:
   -- 1. The smallest X with X*X mod 1_000_000 = 269_696 is at most 99_736.
   -- 2. The largest square X*X, which the program may have to deal with, 
   --    will be at most 9_947_269_69. 
 
   type Number is range 1 .. 99_736*99_736;
   X: Number := 1; 
   -- X can store numbers between 1 and 99_736*99_736. Computations 
   -- involving X can handle intermediate results in that range.
   -- Initially the value stored at X is 1. 
   -- When running the program, the value will become 2, 3, 4, etc. 
 
begin
   -- The program starts running. 
 
   -- The computer first squares X, then it truncates the square, such
   -- that the result is a six-digit number. 
   -- Finally, the computer checks if this number is 269_696. 
   while not (((X*X) mod 1_000_000) = 269_696) loop
 
      -- When the computer goes here, the number was not 269_696. 
      X := X+1; 
      -- So we replace X by X+1, and then go back and try again. 
 
   end loop;
 
   -- When the computer eventually goes here, the number is 269_696.
   -- E.e., the value stored at X is the value we are searching for.
   -- We still have to print out this value. 
 
   Ada.Text_IO.Put_Line(Number'Image(X));
   -- Number'Image(X) converts the value stored at X into a string of 
   -- printable characters (more specifically, of digits). 
   -- Ada.Text_IO.Put_Line(...) prints this string, for humans to read.
   -- I did already run the program, and it did print out 25264. 
end Babbage_Problem;