Babbage problem

Charles Babbage, looking ahead to the sorts of problems his Analytical Engine would be able to solve, gave this example: what is the smallest number 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.

The task is to find out—and to do so, as far as your language allows it, in code that Babbage himself would have been able to read and understand. For these purposes, Charles Babbage may be taken to be an intelligent person, familiar with mathematics and with the idea of a computer, who has never programmed—in fact, who has never so much as seen a single line of code. 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 did indeed solve the specified problem.

BBC BASIC

Clarity has been preferred over all other considerations. The line LET n = n + 1, for instance, would more naturally be written n% += 1, using an integer variable and a less verbose assignment syntax; but this optimization did not seem to justify the additional explanations Professor Babbage would probably need to understand it. <lang bbcbasic>REM Statements beginning 'REM' are explanatory remarks: the machine will ignore them.

REM We shall test values of n from 1 upwards until we find one whose square ends in 269,696.

REM A number that ends in 269,696 is one that leaves a remainder of 269,696 when divided by a million.

REM So we are looking for a number that satisfies the condition 'n squared modulo 1,000,000 = 269,696', or 'n^2 MOD 1000000 = 269696' in the notation that the machine can accept.

REM Observe that in this notation groups of digits may not be separated by commas.

LET n = 0

REPEAT

 LET n = n + 1

UNTIL n^2 MOD 1000000 = 269696

REM 'REPEAT... UNTIL' causes the machine to perform the addition repeatedly until the condition is satisfied.

REM Although n is initially equal to 0, the first number that is actually tested is 1.

REM This is because the addition is carried out before the test.

PRINT "The smallest number whose square ends in 269696 is" n PRINT "Its square is" n^2

REM 'PRINT' causes anything enclosed in double quotation marks to be displayed just as it is written. REM The expressions 'n' and 'n^2' are not so enclosed: they are therefore evaluated, and what is displayed is the result.</lang>

Output:

The smallest number whose square ends in 269696 is     25264
Its square is 638269696

COBOL

<lang cobol>IDENTIFICATION DIVISION. PROGRAM-ID. BABBAGE-PROGRAM.

A line beginning with an asterisk is an explanatory note.
The machine will disregard any such line.

DATA DIVISION. WORKING-STORAGE SECTION.

In this part of the program we reserve the storage space we shall
be using for our variables, using a 'PICTURE' clause to specify
how many digits the machine is to keep free.
The prefixed number 77 indicates that these variables do not form part
of any larger 'record' that we might want to deal with as a whole.

77 N PICTURE 99999.

We know that 99,736 is a valid answer.

77 N-SQUARED PICTURE 9999999999. 77 LAST-SIX PICTURE 999999. PROCEDURE DIVISION.

Here we specify the calculations that the machine is to carry out.

CONTROL-PARAGRAPH.

   PERFORM COMPUTATION-PARAGRAPH VARYING N FROM 1 BY 1
   UNTIL LAST-SIX IS EQUAL TO 269696.
   STOP RUN.

COMPUTATION-PARAGRAPH.

   MULTIPLY N BY N GIVING N-SQUARED.
   MOVE N-SQUARED TO LAST-SIX.

Since the variable LAST-SIX can hold a maximum of six digits,
only the final six digits of N-SQUARED will be moved into it:
the rest will not fit and will simply be discarded.

   IF LAST-SIX IS EQUAL TO 269696 THEN DISPLAY N.</lang>

Output: