

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.




 
/*
This code is an implementation of Babbage Problem in SQL ORACLE 19c 
p_ziel  -- the substring to search for, which can start with leading zeros
p_max   -- upper bound of the cycle
v_max   -- safe determination of the upper bound of the cycle
v_start -- safe starting point
*/
WITH
  FUNCTION babbage(p_ziel IN varchar2, p_max INTEGER) RETURN varchar2 IS
    v_max    INTEGER := greatest(p_max,to_number('1E+'||LENGTH(to_char(p_ziel))));
    v_start  NUMBER := CASE WHEN substr(p_ziel,1,1)='0' THEN CEIL(SQRT('1'||p_ziel)) ELSE CEIL(SQRT(p_ziel)) END;
    v_length NUMBER := to_number('1E+'||LENGTH(to_char(p_ziel)));   
  BEGIN
    -- first check
    IF substr(p_ziel,-1) IN (2,3,7,8) THEN 
      RETURN 'The exact square of an integer cannot end with '''||substr(p_ziel,-1)||''', so there is no such smallest number whose square ends in '''||p_ziel||'''';
    END IF; 
    -- second check
    IF regexp_count(p_ziel,'([^0]0{1,}$)')=1 AND MOD(regexp_count(regexp_substr(p_ziel,'(0{1,}$)'),'0'),2)=1 THEN
      RETURN 'An exact square of an integer cannot end with an odd number of zeros, so there is no such smallest number whose square ends in '''||p_ziel||'''';
    END IF; 
    -- main cycle
    while v_start < v_max loop
      exit WHEN MOD(v_start**2,v_length) = p_ziel;   
      v_start := v_start + 1; 
    END loop;
    -- output 
    IF v_start = v_max THEN
      RETURN 'There is no such smallest number before '||v_max||' whose square ends in '''||p_ziel||'''';
    ELSE 
      RETURN ''||v_start||' is the smallest number, whose square '||regexp_replace(to_char(v_start**2),'(\d{1,})('||p_ziel||')','\1''\2''')||' ends in '''||p_ziel||''''; 
    END IF; 
    --
  END;
 
--Test
SELECT babbage('222',100000) AS res FROM dual
UNION ALL 
SELECT babbage('33',100000) AS res FROM dual
UNION ALL 
SELECT babbage('17',100000) AS res FROM dual
UNION ALL 
SELECT babbage('888',100000) AS res FROM dual
UNION ALL 
SELECT babbage('1000',100000) AS res FROM dual
UNION ALL 
SELECT babbage('000',100000) AS res FROM dual
UNION ALL 
SELECT babbage('269696',100000) AS res FROM dual -- strict Babbage Problem
UNION ALL 
SELECT babbage('269696',10) AS res FROM dual
UNION ALL 
SELECT babbage('169696',10) AS res FROM dual
UNION ALL
SELECT babbage('19696',100000) AS res FROM dual
UNION ALL 
SELECT babbage('04',100000) AS res FROM dual;
 