Babbage problem

From Rosetta Code
Task
Babbage problem
You are encouraged to solve this task according to the task description, using any language you may know.
Charles Babbage
Charles Babbage's analytical engine.

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.

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.


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.

360 Assembly[edit]

An assembler program always seems a bit tricky for non system engineer because it deals directly with the operating system and with the hardware instructions. Here we have a 32-bit computer with 16 32-bit registers. The caller (the operating system to keep it simple) is calling you giving your location address stored in register-15 and has stored in register-14 his return address. To save each program context, register-13 points to a 18 word save area. Do not spend time in understanding the context saving and restoring in the prologue and epilogue part of the program. What you have to know, “360” architecture uses 32-bit signed binary arithmetic, so here the maximum integer value is 2^31-1 (2147483647). Therefore the solution must be less than 2147483647. The multiplication and the division use a pair of registers; coding “MR 4,2” means multiply register-5 by register-2 and place result in the (register-4,register-5) pair; the same way “DR 4,2” means divide the (register-4,register-5) pair by register-2 and place the quotient in register-5 and the reminder in register-4. We use in the below program this intermediate 64-bit integers to find a solution with a value up to 2^31-1 even when we have to compute the square of this value.

 
* Find the lowest positive integer whose square ends in 269696
* The logic of the assembler program is simple :
* loop for i=524 step 2
* if (i*i modulo 1000000)=269696 then leave loop
* next i
* output 'Solution is: i=' i ' (i*i=' i*i ')'
BABBAGE CSECT beginning of the control section
USING BABBAGE,13 define the base register
B 72(15) skip savearea (72=18*4)
DC 17F'0' savearea (18 full words (17+1))
STM 14,12,12(13) prolog: save the caller registers
ST 13,4(15) prolog: link backwards
ST 15,8(13) prolog: link forwards
LR 13,15 prolog: establish addressability
LA 6,524 let register6 be i and load 524
LOOP LR 5,6 load register5 with i
MR 4,6 multiply register5 with i
LR 7,5 load register7 with the result i*i
D 4,=F'1000000' divide register5 with 1000000
C 4,=F'269696' compare the reminder with 269696
BE ENDLOOP if equal branch to ENDLOOP
LA 6,2(6) load register6 (i) with value i+2
B LOOP branch to LOOP
ENDLOOP XDECO 6,BUFFER+15 edit registrer6 (i)
XDECO 7,BUFFER+34 edit registrer7 (i squared)
XPRNT BUFFER,L'BUFFER print buffer
L 13,4(0,13) epilog: restore the caller savearea
LM 14,12,12(13) epilog: restore the caller registers
XR 15,15 epilog: set return code to 0
BR 14 epilog: branch to caller
BUFFER DC CL80'Solution is: i=............ (i*i=............)'
END BABBAGE end of the control section
 
Output:
Solution is: i=       25264  (i*i=   638269696)


Ada[edit]

-- 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, ect.
 
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;

ALGOL 68[edit]

As with other samples, we use "simple" forms such as "a := a + 1" instead of "a +:= 1".

COMMENT text between pairs of words 'comment' in capitals are
for the human reader's information and are ignored by the machine
COMMENT
 
COMMENT Define s to be the integer value 269 696 COMMENT
INT s = 269 696;
 
COMMENT Name a location in the machine's storage area that will be
used to hold integer values.
The value stored in the location will change during the
calculations.
Note, "*" is used to represent the multiplication operator.
":=" causes the location named to the left of ":=" to
assume the value computed by the expression to the right.
"sqrt" computes an approximation to the square root
of the supplied parameter
"MOD" is an operator that computes the modulus of its
left operand with respect to its right operand
"ENTIER" is a unary operator that yields the largest
integer that is at most its operand.
COMMENT
INT v := ENTIER sqrt( s );
 
COMMENT the construct: WHILE...DO...OD repeatedly executes the
instructions between DO and OD, the execution stops when
the instructions between WHILE and DO yield the value FALSE.
COMMENT
WHILE ( v * v ) MOD 1 000 000 /= s DO v := v + 1 OD;
 
COMMENT print displays the values of its parameters
COMMENT
print( ( v, " when squared is: ", v * v, newline ) )
Output:
     +25264 when squared is:  +638269696

APL[edit]

If at all possible, I would sit down at a terminal with Babbage and invite him to experiment with the various functions used in the program.

      ⍝ We know that 99,736 is a valid answer, so we only need to test the positive integers from 1 up to there:
N←⍳99736
⍝ The SQUARE OF omega is omega times omega:
SQUAREOF←{⍵×⍵}
⍝ To say that alpha ENDS IN the six-digit number omega means that alpha divided by 1,000,000 leaves remainder omega:
ENDSIN←{(1000000|⍺)=⍵}
⍝ The SMALLEST number WHERE some condition is met is found by taking the first number from a list of attempts, after rearranging the list so that numbers satisfying the condition come before those that fail to satisfy it:
SMALLESTWHERE←{1↑⍒⍵}
⍝ We can now ask the computer for the answer:
SMALLESTWHERE (SQUAREOF N) ENDSIN 269696
Output:
25264

AppleScript[edit]

AppleScript's number types are at their limits here, but we can just get to the first Babbage number, after 638 integer root tests on suffixed numbers:

-- BABBAGE -------------------------------------------------------------------
 
-- babbage :: Int -> [Int]
on babbage(intTests)
 
script test
on toSquare(x)
(x * 1000000) + 269696
end toSquare
 
on |λ|(x)
hasIntRoot(toSquare(x))
end |λ|
end script
 
script toRoot
on |λ|(x)
((x * 1000000) + 269696) ^ (1 / 2)
end |λ|
end script
 
set xs to filter(test, enumFromTo(1, intTests))
zip(map(toRoot, xs), map(test's toSquare, xs))
end babbage
 
-- TEST ----------------------------------------------------------------------
on run
-- Try 1000 candidates
 
unlines(map(curry(intercalate)'s |λ|(" -> "), babbage(1000)))
 
--> "2.5264E+4 -> 6.38269696E+8"
end run
 
 
-- GENERIC FUNCTIONS ---------------------------------------------------------
 
-- curry :: (Script|Handler) -> Script
on curry(f)
script
on |λ|(a)
script
on |λ|(b)
|λ|(a, b) of mReturn(f)
end |λ|
end script
end |λ|
end script
end curry
 
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m > n then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end enumFromTo
 
-- filter :: (a -> Bool) -> [a] -> [a]
on filter(f, xs)
tell mReturn(f)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter
 
-- hasIntRoot :: Int -> Bool
on hasIntRoot(n)
set r to n ^ 0.5
r = (r as integer)
end hasIntRoot
 
-- intercalate :: Text -> [Text] -> Text
on intercalate(strText, lstText)
set {dlm, my text item delimiters} to {my text item delimiters, strText}
set strJoined to lstText as text
set my text item delimiters to dlm
return strJoined
end intercalate
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
 
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
 
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property |λ| : f
end script
end if
end mReturn
 
-- unlines :: [String] -> String
on unlines(xs)
intercalate(linefeed, xs)
end unlines
 
-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
set lng to min(length of xs, length of ys)
set lst to {}
repeat with i from 1 to lng
set end of lst to {item i of xs, item i of ys}
end repeat
return lst
end zip
Output:
2.5264E+4  ->  6.38269696E+8

AutoHotkey[edit]

 
; Give n and initial value
n = 519
 
; Loop this action while condition is not satisfied
while (Mod(n*n, 1000000) != 269696) {
; Increment n
n++
}
 
; Display n as value
msgbox, %n%
 
Output:
25264

AWK[edit]

 
# A comment starts with a "#" and are ignored by the machine. They can be on a
# line by themselves or at the end of an executable line.
#
# A program consists of multiple lines or statements. This program tests
# positive integers starting at 1 and terminates when one is found whose square
# ends in 269696.
#
# The next line shows how to run the program.
# syntax: GAWK -f BABBAGE_PROBLEM.AWK
#
BEGIN { # start of program
# this declares a variable named "n" and assigns it a value of zero
n = 0
# do what's inside the "{}" until n times n ends in 269696
do {
n = n + 1 # add 1 to n
} while (n*n !~ /269696$/)
# print the answer
print("The smallest number whose square ends in 269696 is " n)
print("Its square is " n*n)
# terminate program
exit(0)
} # end of program
 

Output:

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

Batch File[edit]


:: This line is only required to increase the readability of the output by hiding the lines of code being executed

@echo off

:: Everything between the lines keeps repeating until the answer is found

:: The code works by, starting at 1, checking to see if the last 6 digits of the current number squared is equal to 269696
::----------------------------------------------------------------------------------
:loop
:: Increment the current number being tested by 1
set /a number+=1

:: Square the current number

set /a numbersquared=%number%*%number%

:: Check if the last 6 digits of the current number squared is equal to 269696, and if so, stop looping and go to the end

if %numbersquared:~-6%==269696 goto end
 
goto loop
::----------------------------------------------------------------------------------
 
:end
echo %number% * %number% = %numbersquared%
pause>nul
 
Output:
25264 * 25264 = 638269696

BBC BASIC[edit]

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.

REM Statements beginning 'REM' are explanatory remarks: the machine will ignore them.
 
REM We shall test positive integers 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 value of n 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.
 
LET n = 0
 
REPEAT
LET n = n + 1
UNTIL n^2 MOD 1000000 = 269696
 
PRINT "The smallest number whose square ends in 269696 is" n
 
PRINT "Its square is" n^2
Output:
The smallest number whose square ends in 269696 is     25264
Its square is 638269696

Alternative method[edit]

Translation of: PowerShell

The algorithm given in the alternative PowerShell implementation may be substantially more efficient, depending on how long SQR takes, and I think could well be more comprehensible to Babbage.

REM Lines that begin 'REM' are explanatory remarks addressed to the human reader.
 
REM The machine will ignore them.
 
LET n = 269696
 
REPEAT
 
LET n = n + 1000000
 
REM Find the next number that ends in 269,696.
 
REM The function SQR finds the square root.
 
LET root = SQR n
 
REM The function INT truncates a real number to an integer.
 
UNTIL root = INT root
 
REM If the square root is equal to its integer truncation, then it is an integer: so we have found our answer.
 
PRINT "The smallest number whose square ends in 269696 is" root
 
PRINT "Its square is" n
Output:

Identical to the first BBC BASIC version.

C[edit]

 
// This code is the implementation of Babbage Problem
 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int main() {
int current = 0, //the current number
square; //the square of the current number
 
//the strategy of take the rest of division by 1e06 is
//to take the a number how 6 last digits are 269696
while ((current*current % 1000000 != 269696) && (square<INT_MAX)) {
current++;
}
 
//output
if (square>+INT_MAX)
printf("Condition not satisfied before INT_MAX reached.");
else
printf ("The smallest number whose square ends in 269696 is %d\n", current);
 
//the end
return 0 ;
}
 
Output:
The smallest number whose square ends in 269696 is 25264

Common Lisp[edit]

 
(defun babbage-test (n)
"A generic function for any ending of a number"
(when (> n 0)
(do* ((i 0 (1+ i))
(d (expt 10 (1+ (truncate (log n) (log 10))))) )
((= (mod (* i i) d) n) i) )))
 
 
Output:
(babbage-test 269696)
25264


C++[edit]

#include <iostream>
 
int main( ) {
int current = 0 ;
while ( ( current * current ) % 1000000 != 269696 )
current++ ;
std::cout << "The square of " << current << " is " << (current * current) << " !\n" ;
return 0 ;
}
Output:
The square of 25264 is 638269696 !

C#[edit]

namespace Babbage_Problem
{
class iterateNumbers
{
public iterateNumbers()
{
long baseNumberSquared = 0; //the base number multiplied by itself
long baseNumber = 0; //the number to be squared, this one will be iterated
 
do //this sets up the loop
{
baseNumber += 1; //add one to the base number
baseNumberSquared = baseNumber * baseNumber; //multiply the base number by itself and store the value as baseNumberSquared
}
while (Right6Digits(baseNumberSquared) != 269696); //this will continue the loop until the right 6 digits of the base number squared are 269,696
 
Console.WriteLine("The smallest integer whose square ends in 269,696 is " + baseNumber);
Console.WriteLine("The square is " + baseNumberSquared);
 
}
 
private long Right6Digits(long baseNumberSquared)
{
 
string numberAsString = baseNumberSquared.ToString(); //this is converts the number to a different type so it can be cut up
 
if (numberAsString.Length < 6) { return baseNumberSquared; }; //if the number doesn't have 6 digits in it, just return it to try again.
 
numberAsString = numberAsString.Substring(numberAsString.Length - 6); //this extracts the last 6 digits from the number
 
return long.Parse(numberAsString); //return the last 6 digits of the number
 
}
}
}}
Output:
The smallest integer whose square ends in 269,696 is 25264
The square is 638269696

Clojure[edit]

; Defines function named babbage? that returns true if the
; square of the provided number leaves a remainder of 269,696 when divided
; by a million
(defn babbage? [n]
(let [square (expt n 2)]
(= 269696 (mod square 1000000))))
 
; Given a range of positive integers up to 99,736, apply the above babbage?
; function, returning only numbers that return true.
(filter babbage? (range 99736))
Output:
(25264)


COBOL[edit]

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.
Output:
25264

D[edit]

// It's basically the same as any other version.
// What can be observed is that 269696 is even, so we have to consider only even numbers,
// because only the square of even numbers is even.
 
import std.math;
import std.stdio;
 
void main( )
{
// get smallest number <= sqrt(269696)
int k = cast(int)(sqrt(269696.0));
 
// if root is odd -> make it even
if (k % 2 == 1)
k = k - 1;
 
// cycle through numbers
while ((k * k) % 1000000 != 269696)
k = k + 2;
 
// display output
writefln("%d * %d = %d", k, k, k*k);
}
Output:
25264 * 25264 = 638269696

Dafny[edit]

 
// Helper function for mask: does the actual computation.
function method mask_(v:int,m:int):int
decreases v-m
requires 0 <= v && 0 < m
ensures v < mask_(v,m)
{
if v < m then m else mask_(v,m*10)
}
 
// Return the smallest power of 10 greater than v.
function method mask(v:int):int
requires 0 <= v
ensures v < mask(v)
{
mask_(v,10)
}
 
// Return true if the last digits of v == suffix.
predicate method EndWith(v:int,suffix:int)
requires 0 <= suffix
{
v % mask(suffix) == suffix
}
 
method SmallestSqEndingWith(suffix:int) returns (s:int)
requires 0 < suffix
ensures EndWith(s*s, suffix)
// ensures forall i :: 0 <= i < s ==> !EndWith(i*i,suffix)
decreases * // This method may not terminate.
{
s := 0;
// squares is the sequence of s*s. A ghost variable is only used by the
// verification process at compile time.
ghost var squares := [];
while !EndWith(s*s, suffix)
invariant s == |squares|
invariant forall i :: 0 <= i < s ==> squares[i] == i*i && !EndWith(squares[i], suffix)
decreases *
{
squares := squares + [s*s];
s := s + 1;
}
// Leaving the method:
// s*s ends with the suffix.
assert EndWith(s*s, suffix);
// The sequence squares contains i*i for i in [0..s]; none of the elements of
// squares ends with the suffix.
assert s == |squares|;
assert forall i :: 0 <= i < s ==> i*i == squares[i] && !EndWith(squares[i], suffix);
// That last assertion should imply the commented-out post-condition of the
// method, but I'm not sure how to express that.
//
// Conclusion: s is guaranteed to be the smallest number whose square ends
// with the suffix.
}
 
method Main() decreases *
{
var suffix := 269696;
var smallest := SmallestSqEndingWith(suffix);
print smallest, "\n";
}
 


Dart[edit]

 
 
 
main() {
var x = 0;
while((x*x)% 1000000 != 269696)
{ x++;}
 
print('$x');
}
 

Elixir[edit]

defmodule Babbage do
def problem(n) when rem(n*n,1000000)==269696, do: n
def problem(n), do: problem(n+2)
end
 
IO.puts Babbage.problem(0)

or

Stream.iterate(2, &(&1+2))
|> Enum.find(&rem(&1*&1, 1000000) == 269696)
|> IO.puts
Output:
25264

Erlang[edit]

 
-module(solution1).
-export([main/0]).
babbage(N,E) when N*N rem 1000000 == 269696 ->
io:fwrite("~p",[N]);
babbage(N,E) ->
case E of
4 -> babbage(N+2,6);
6 -> babbage(N+8,4)
end.
main()->
babbage(4,4).
 

F#[edit]

 
let mutable n=1
while(((n*n)%( 1000000 ))<> 269696) do
n<-n+1
printf"%i"n
 

Forth[edit]

Can a Forth program be made readable to a novice, without getting into what a stack is? We shall see.

( First we set out the steps the computer will use to solve the problem )
 
: BABBAGE
1 ( start from the number 1 )
BEGIN ( commence a "loop": the computer will return to this point repeatedly )
1+ ( add 1 to our number )
DUP DUP ( duplicate the result twice, so we now have three copies )
( We need three because we are about to multiply two of them together to find the square, and the third will be used the next time we go around the loop -- unless we have found our answer, in which case we shall need to print it out )
* ( * means "multiply", so we now have the square )
1000000 MOD ( find the remainder after dividing it by a million )
269696 = ( is it equal to 269,696? )
UNTIL ( keep repeating the steps from BEGIN until the condition is satisfied )
. ; ( when it is satisfied, print out the number that allowed us to satisfy it )
 
( Now we ask the machine to carry out these instructions )
 
BABBAGE
Output:
25264

FreeBASIC[edit]

' version 25-10-2016
' compile with: fbc -s console
 
' Charles Babbage would have known that only number ending
' on a 4 or 6 could produce a square ending on a 6
' also any number below 520 would produce a square smaller than 269,696
' we can stop when we have reached 99,736
' we know it square and it ends on 269,696
 
Dim As ULong number = 524 ' first number to try
Dim As ULong square, count
 
Do
' square the number
square = number * number
' look at the last 6 digits, if they match print the number
If Right(Str(square), 6) = "269696" Then Exit Do
' increase the number with 2, number end ons a 6
number = number +2
' if the number = 99736 then we haved found a smaller number, so stop
If number = 99736 Then Exit Do
square = number * number
' look at the last 6 digits, if they match print the number
If Right(Str(square),6 ) = "269696" Then Exit Do
' increase the number with 8, number ends on a 4
number = number +8
' go to the first line under "Do"
Loop
 
If number = 99736 Then
Print "No smaller number was found"
Else
' we found a smaller number, print the number and its square
Print Using "The number = #####, and its square = ##########,"; number; square
End If
 
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
The number = 25,264 and its square = 638,269,696

FutureBasic[edit]

include "ConsoleWindow"
 
DIM AS LONG i
 
FOR i = 1 TO 1000000
IF i ^ 2 MOD 1000000 == 269696 THEN EXIT FOR
NEXT
 
PRINT "The smallest number whose square ends in 269696 is"; i
PRINT "Its square is"; i ^ 2
Output:
The smallest number whose square ends in 269696 is 25264
Its square is 638269696

Go[edit]

package main
 
import "fmt"
import "math"
 
func main() {
 
var MAX, c, d, current float64
current = 0
MAX = 9223372036854775806
for d != 269696 && c < MAX {
c = current * current
d = math.Mod(c, 1000000)
current++
}
if c > MAX {
fmt.Println("not calculatable")
} else {
fmt.Println("The smallest number whose square ends with 269696 is",
current-1)
}
}
Output:
The smallest number whose square ends with 269696 is 25264

Groovy[edit]

 
int n=104; ///starting point
while( (n**2)%1000000 != 269696 )
{ if (n%10==4) n=n+2;
if (n%10==6) n=n+8;
}
println n+"^2== "+n**2 ;
 
Output:
25264^2== 638269696

Haskell[edit]

head[edit]

--Calculate squares, testing for the last 6 digits
findBabbageNumber :: Integer
findBabbageNumber =
head (filter ((269696 ==) . flip mod 1000000 . (^ 2)) [1 ..])
 
main :: IO ()
main =
(putStrLn . unwords)
(zipWith
(++)
(show <$> ([id, (^ 2)] <*> [findBabbageNumber]))
[" ^ 2 equals", " !"])
Output:
25264 ^ 2 equals 638269696 !

Safe.headMay[edit]

Or, if we incline to the nullius in verba approach, are not yet convinced that there really are any such numbers below 100,000, and look uncertainly at head – a partial function which simply fails on empty lists, we could import the Safe module, and use the headMay alternative, which, more cautiously and experimentally, returns a Maybe value:

import Data.List (intercalate)
import Safe (headMay)
 
maybeBabbage :: Integer -> Maybe Integer
maybeBabbage upperLimit =
headMay
(filter ((269696 ==) . flip rem 1000000) ((^ 2) <$> [1 .. upperLimit]))
 
main :: IO ()
main = do
let upperLimit = 100000
putStrLn
(case maybeBabbage upperLimit of
Nothing ->
intercalate (show upperLimit) ["No such number found below ", " ..."]
Just x ->
intercalate
" ^ 2 -> "
(fmap show ([floor . sqrt . fromInteger, id] <*> pure x)))
Output:
25264 ^ 2  ->  638269696

Suffixes and integer roots[edit]

The inverse approach, which gets us to the first number in just 638 tests, is to append a 269696 suffix to each successive integer, filtering for results with integer square roots.

We can then harvest as many as we need from an infinite stream of babbages, Mr Babbage.

import Data.List (intercalate)
 
babbagePairs :: [[Integer]]
babbagePairs =
[0,1000000 ..] >>= -- Drawing from a succession of N * 10^6
\x ->
let y = (x + 269696) -- The next number ending in 269696,
r = (sqrt . fromIntegral) y -- its square root,
i = floor r -- and the integer part of that root.
in [ [i, y] -- Root and square harvested together,
| r == fromIntegral i ] -- only if that root is an integer.
 
 
main :: IO ()
main = do
let arrowed = intercalate " ^ 2 -> " . fmap show
mapM_ putStrLn (arrowed <$> take 10 babbagePairs)
Output:
25264 ^ 2 -> 638269696
99736 ^ 2 -> 9947269696
150264 ^ 2 -> 22579269696
224736 ^ 2 -> 50506269696
275264 ^ 2 -> 75770269696
349736 ^ 2 -> 122315269696
400264 ^ 2 -> 160211269696
474736 ^ 2 -> 225374269696
525264 ^ 2 -> 275902269696
599736 ^ 2 -> 359683269696

A quick glance at these results suggests that Mr Babbage would have done well to inspect more closely the way in which the final digits of the square constrain the final digits of the root.

We can get to the solution almost immediately, after only a handful of tests, well within the reach of pencil and paper, if we discern that the root itself, to produce the 269692 suffix in its square, must have one of only four different final digit sequences: (0264, 5264, 4736, or 9736).

With a machine, this approach can industrialise the babbage harvest, yielding thousands of pairs in less than a second:

import Data.List (intercalate)
 
babbagePairs :: [[Integer]]
babbagePairs =
[0,10000 ..] >>=
\x ->
([(:) <*> return . (^ 2)] <*> ((x +) <$> [0264, 5264, 9736, 4736])) >>=
\[a, b] ->
[ [a, b]
| ((269696 ==) . flip rem 1000000) b ]
 
main :: IO ()
main = do
let arrowed = intercalate " ^ 2 -> " . fmap show
mapM_ putStrLn (arrowed <$> take 4000 babbagePairs)

J[edit]

The key to understandability is a mix of hopefully adequate notation and some level of verifiability.

So let's break the implementation into some named pieces and present enough detail that a mathematician can verify that the result is both consistent and reasonable:

   square=: ^&2
modulo1e6=: 1000000&|
trythese=: i. 1000000 NB. first million nonnegative integers
which=: I. NB. position of true values
which 269696=modulo1e6 square trythese NB. right to left <-
25264 99736 150264 224736 275264 349736 400264 474736 525264 599736 650264 724736 775264 849736 900264 974736

The smallest of these values is 25264.

Java[edit]

public class Test {
 
public static void main(String[] args) {
 
// let n be zero
int n = 0;
 
// repeat the following action
do {
 
// increase n by 1
n++;
 
// while the modulo of n times n is not equal to 269696
} while (n * n % 1000_000 != 269696);
 
// show the result
System.out.println(n);
}
}
25264

JavaScript[edit]

Iteration[edit]

// Every line starting with a double slash will be ignored by the processing machine,
// just like these two.
//
// Since the square root of 269,696 is approximately 519, we create a variable named "n"
// and give it this value.
n = 519
 
// The while-condition is in parentheses
// * is for multiplication
// % is for modulo operation
// != is for "not equal"
while ( ((n * n) % 1000000) != 269696 )
n = n + 1
 
// n is incremented until the while-condition is met, so n should finally be the
// smallest positive integer whose square ends in the digits 269,696. To see n, we
// need to send it to the monitoring device (named console).
console.log(n)
 

Array constructor[edit]

JavaScript's Array constructor lets us filter an array automatically populated with a function of the element index. This proves faster than setting up and running a while loop test, and we can make it particularly efficient by testing the potential squares rather than the potential roots.

Starting with numbers which end in 269696, and filtering for those which have integer roots, so that we reach 25264 ^2 -> 638269696 after only 638 tests.

Works with: ES6
(() => {
// BABBAGE ---------------------------------------------------------------
 
// babbageNumbers :: Int -> [(Int, Int)]
const babbageNumbers = intTests => {
return map(x => [Math.sqrt(x), x], filter(
hasIntegerRoot,
takeNfromSeries(intTests, x => (x * 1000000) + 269696)
));
};
 
// hasIntegerRoot :: Int -> Bool
const hasIntegerRoot = n => {
const r = Math.sqrt(n);
return Math.floor(r) === r;
};
 
// takeNFromSeries :: Int -> (Int -> a) -> [a]
const takeNfromSeries = (n, f) =>
Array.from({
length: n
}, (_, i) => f(i));
 
// GENERIC FUNCTIONS -----------------------------------------------------
 
// curry :: ((a, b) -> c) -> a -> b -> c
const curry = f => a => b => f(a, b);
 
// filter :: (a -> Bool) -> [a] -> [a]
const filter = (f, xs) => xs.filter(f);
 
// intercalate :: String -> [a] -> String
const intercalate = (s, xs) => xs.join(s);
 
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);
 
// unlines :: [String] -> String
const unlines = xs => xs.join('\n');
 
// TEST ------------------------------------------------------------------
return unlines(
map(
curry(intercalate)(' ^2 -> '),
babbageNumbers(1000000) // Testing 10^6 numbers ending in 269696
)
);
})();
Output:
25264 ^2 -> 638269696
99736 ^2 -> 9947269696
150264 ^2 -> 22579269696
224736 ^2 -> 50506269696
275264 ^2 -> 75770269696
349736 ^2 -> 122315269696
400264 ^2 -> 160211269696
474736 ^2 -> 225374269696
525264 ^2 -> 275902269696
599736 ^2 -> 359683269696
650264 ^2 -> 422843269696
724736 ^2 -> 525242269696
775264 ^2 -> 601034269696
849736 ^2 -> 722051269696
900264 ^2 -> 810475269696
974736 ^2 -> 950110269696

Kotlin[edit]

// version 1.0.6 (Kotlin is under active development and this is the latest stable version)
 
// All Kotlin programs start from a 'main' function' and comments - like this one - start with a double slash.
 
fun main(args: Array<String>) { // don't worry what 'args' is as it's not needed here
// We will start looking at integer numbers from 520 onwards as the square root of 269696 is just under that.
// Also the latter is an even number and so its square root must be even also.
 
// Declare some variables first to hold each number and its square.
var number: Long = 520 // 'number' is a long integer variable which initially has a value of 520
var square: Long = 520 * 520 // 'square' is a long integer variable containing number's square
 
while (true) { // keep checking numbers indefinitely until we find one which solves the problem
// examine the last 6 digits of 'square' by converting it first to a string of digits
val last6 = square.toString().takeLast(6)
// check if 'last6' is equal to "269696"
if (last6 == "269696") { // we've found the smallest number which solves the problem!
println ("The smallest number is $number whose square is $square") // print the answer to the terminal
return // return from the 'main' function which ends the program
}
number = number + 2 // otherwise add 2 to get next even number
square = number * number // and square it before the next test
}
}
Output:
The smallest number is 25264 whose square is 638269696

Liberty BASIC[edit]

Now Mr. Babbage -- May I call you Charlie? No. OK -- we'll first start with 'n' equal to zero, then multiply it by itself to square it. If the last six digits of the result are not 269696, we'll add one to 'n' then go back and square it again. On our modern computer it should only take a moment to find the answer...

 
[start]
if right$(str$(n*n),6)="269696" then
print "n = "; using("###,###", n);
print " n*n = "; using("###,###,###,###", n*n)
end if
if n<100000 then n=n+1: goto [start]
print "Program complete."
 

Eureka! We found it! --

 
n = 25,264 n*n = 638,269,696
n = 99,736 n*n = 9,947,269,696
Program complete.
 

Now my question for you, Sir, is how did you know that the square of ANY number would end in 269696?? Oh, and by the way, 99,736 is an answer too.

Mathematica[edit]

Solving up to his guess would show that there is indeed a smaller integer with that property.

 Solve[Mod[x^2, 10^6] == 269696 && 0 <= x <= 99736, x, Integers]
Output:
{{x->25264},{x->99736}}

NetRexx[edit]

Translation of: Groovy
/* NetRexx */
options replace format comments java crossref symbols nobinary utf8
numeric digits 5000 -- set up numeric precision
 
babbageNr = babbage() -- call a function to perform the analysis and capture the result
babbageSq = babbageNr ** 2 -- calculate the square of the result
-- display results using a library function
System.out.printf("%,10d\u00b2 == %,12d%n", [Integer(babbageNr), Integer(babbageSq)])
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- A function method to answer Babbage's question:
-- "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.)
 
method babbage() public static binary
n = int 104 -- (integer arithmatic)
-- begin a processing loop to determine the value
-- starting point: 104
loop while ((n * n) // 1000000) \= 269696
-- loop continues while the remainder of n squared divided by 1,000,000 is not equal to 269,696
if n // 10 == 4 then do
-- increment n by 2 if the remainder of n divided by 10 equals 4
n = n + 2
end
if n // 10 == 6 then do
-- increment n by 8 if the remainder of n divided by 10 equals 6
n = n + 8
end
end
 
return n -- end the function and return the result
 
Output:
    25,264² ==  638,269,696

OCaml[edit]

 
let rec f a=
if (a*a) mod 1000000 != 269696
then f(a+1)
else a
in
let a= f 1 in
Printf.printf "smallest positive integer whose square ends in the digits 269696 is %d\n" a
 

PARI/GP[edit]

m=269696;
k=1000000;
{for(n=1,99736,
\\ Try each number in this range, from 1 to 99736
if(denominator((n^2-m)/k)==1, \\ Check if n squared, minus m, is divisible by k
return(n) \\ If so, return this number and STOP.
)
)}


Pascal[edit]

program BabbageProblem;
(* Anything bracketed off like this is an explanatory comment. *)
var n : longint; (* The VARiable n can hold a 'long', ie large, INTeger. *)
begin
n := 2; (* Start with n equal to 2. *)
repeat
n := n + 2 (* Increase n by 2. *)
until (n * n) mod 1000000 = 269696;
(* 'n * n' means 'n times n'; 'mod' means 'modulo'. *)
write(n)
end.
Output:
25264

Perl[edit]

#!/usr/bin/perl
use strict ;
use warnings ;
 
my $current = 0 ;
while ( ($current ** 2 ) % 1000000 != 269696 ) {
$current++ ;
}
print "The square of $current is " . ($current * $current) . " !\n" ;
Output:
The square of 25264 is 638269696 !

Perl 6[edit]

Works with: Rakudo version 2016.03

This could certainly be written more concisely. Extra verbiage is included to make the process more clear.

# For all positives integers from 1 to Infinity
for 1 .. Inf -> $integer {
 
# calculate the square of the integer
my $square = $integer²;
 
# print the integer and square and exit if the square modulo 1000000 is equal to 269696
print "{$integer}² equals $square" and exit if $square mod 1000000 == 269696;
}
Output:
25264² equals 638269696

Alternatively, the following just may be declarative enough to allow Babbage to understand what's going on:

say $_ if ($_²  % 1000000 == 269696) for 1..99736;
Output:
25264
99736

Phix[edit]

We can omit anything odd, as any odd number squared is obviously always odd.
Mr Babbage might need the whole "i is a variable" thing explained, and that "?i" prints the value of i, nowt else springs to mind.

for i=2 to 99736 by 2 do
if remainder(i*i,1000000)=269696 then ?i exit end if
end for
Output:
25264

PicoLisp[edit]

: (for N 99736                               # Iterate N from 1 to 99736
(T (= 269696 (% (* N N) 1000000)) N) ) # Stop if remainder is 269696
-> 25264

PowerShell[edit]

 
###########################################################################################
#
# Definitions:
#
# Lines that begin with the "#" symbol are comments: they will be ignored by the machine.
#
# -----------------------------------------------------------------------------------------
#
# While
#
# Run a command block based on the results of a conditional test.
#
# Syntax
# while (condition) {command_block}
#
# Key
#
# condition If this evaluates to TRUE the loop {command_block} runs.
# when the loop has run once the condition is evaluated again.
#
# command_block Commands to run each time the loop repeats.
#
# As long as the condition remains true, PowerShell reruns the {command_block} section.
#
# -----------------------------------------------------------------------------------------
#
# * means 'multiplied by'
#  % means 'modulo', or remainder after division
# -ne means 'is not equal to'
# ++ means 'increment variable by one'
#
###########################################################################################
 
# Declare a variable, $integer, with a starting value of 0.
 
$integer = 0
 
while (($integer * $integer) % 1000000 -ne 269696)
{
$integer++
}
 
# Show the result.
 
$integer
 
Output:
25264

Alternative method

Works with: PowerShell version 2

By looping through potential squares instead of potential square roots, we reduce the number of loops by a factor of 40.

#  Start with the smallest potential square number
$TestSquare = 269696
 
# Test if our potential square is a square
# by testing if the square root of it is an integer
# Test if the square root is an integer by testing if the remainder
# of the square root divided by 1 is greater than zero
#  % is the remainder operator
# -gt is the "greater than" operator
 
# While the remainder of the square root divided by one is greater than zero
While ( [Math]::Sqrt( $TestSquare ) % 1 -gt 0 )
{
# Add 100,000 to get the next potential square number
$TestSquare = $TestSquare + 1000000
}
# This will loop until we get a value for $TestSquare that is a square number
 
# Caclulate the root
$Root = [Math]::Sqrt( $TestSquare )
 
# Display the result and its square
$Root
$TestSquare
Output:
25264
638269696

Processing[edit]

// Lines that begin with two slashes, thus, are comments: they
// will be ignored by the machine.
 
// First we must declare a variable, n, suitable to store an integer:
 
int n;
 
// Each statement we address to the machine must end with a semicolon.
 
// To begin with, the value of n will be zero:
 
n = 0;
 
// Now we must repeatedly increase it by one, checking each time to see
// whether its square ends in 269,696.
 
// We shall do this by seeing whether the remainder, when n squared
// is divided by one million, is equal to 269,696.
 
do {
n = n + 1;
} while (n * n % 1000000 != 269696);
 
// To read this formula, it is necessary to know the following
// elements of the notation:
// * means 'multiplied by'
//  % means 'modulo', or remainder after division
//  != means 'is not equal to'
 
// Now that we have our result, we need to display it.
 
// println is short for 'print line'
 
println(n);
Output:
25264

Python[edit]

 
# Lines that start by # are a comments:
# they will be ignored by the machine
 
n=0 # n is a variable and its value is 0
 
# we will increase its value by one until
# its square ends in 269,696
 
while n**2 % 1000000 != 269696:
 
# n**2 -> n squared
# % -> 'modulo' or remainer after division
# != -> not equal to
 
n += 1 # += -> increase by a certain number
 
print(n) # prints n
 
Output:
25264

Racket[edit]

;; Text from a semicolon to the end of a line is ignored
;; This lets the racket engine know it is running racket
#lang racket
 
;; “define” defines a function in the engine
;; we can use an English name for the function
;; a number ends in 269696 when its remainder when
;; divided by 1000000 is 269696 (we omit commas in
;; numbers... they are used for another reason).
(define (ends-in-269696? x)
(= (remainder x 1000000) 269696))
 
;; we now define another function square-ends-in-269696?
;; actually this is the composition of ends-in-269696? and
;; the squaring function (which is called “sqr” in racket)
(define square-ends-in-269696? (compose ends-in-269696? sqr))
 
;; a for loop lets us iterate (it’s a long Latin word which
;; Victorians are good at using) over a number range.
;;
;; for/first go through the range and break when it gets to
;; the first true value
;;
;; (in-range a b) produces all of the integers from a (inclusive)
;; to b (exclusive). Because we know that 99736² ends in 269696,
;; we will stop there. The add1 is to make in-range include 99736
;;
;; we define a new variable, so that we can test the verity of
;; our result
(define first-number-that-when-squared-ends-in-269696
(for/first ((i ; “i” will become the ubiquetous looping variable of the future!
(in-range 1 (add1 99736)))
 ; when returns when only the first one that matches
#:when (square-ends-in-269696? i))
i))
 
;; display prints values out; newline writes a new line (otherwise everything
;; gets stuck together)
(display first-number-that-when-squared-ends-in-269696)
(newline)
(display (sqr first-number-that-when-squared-ends-in-269696))
(newline)
(newline)
(display (ends-in-269696? (sqr first-number-that-when-squared-ends-in-269696)))
(newline)
(display (square-ends-in-269696? first-number-that-when-squared-ends-in-269696))
(newline)
;; that all seems satisfactory
Output:
25264
638269696

#t
#t

R[edit]

 
babbage_function=function(){
n=0
while (n**2%%1000000!=269696) {
n=n+1
}
return(n)
}
babbage_function()[length(babbage_function())]
 
Output:
25264

REXX[edit]

If this were a computer program to be shown to a computer programming novice   (albeit a very
intelligent polymath novice),   the computer program would also have a   lot   more comments,
notes, and accompanying verbiage which would/could/should explain:

  •   what a (computer program) comment looks like
  •   what a computer is
  •   what a computer program is
  •   how a computer stores numbers and such
  •   what are   variables   and how to store   stuff in them
  •   how the   do   loop works (initial value, incrementation, etc)
  •   how an assignment   =   operator works
  •   how a comparison   ==   operator works
  •   how an   if   statement works
  •   what a (computer program) statement is
  •   what the   *   operator is and how it does multiplication
  •   what the   +   operator is and how it does addition
  •   what the   //   operator is and how it does division remainder
  •   what the   right   BIF does
  •   who what a   BIF   is and how it returns a value
  •   how/when the   then   cause gets executed   (after an   if)
  •   explain how/why an   end   statement is needed for a   do   loop
  •   explain how a   leave   statement works
  •   ··· the   say   is probably the only statement that is self-explanatory

examine the right-most 6 digits of square[edit]

/*REXX program finds the  lowest (positive)  integer  whose  square  ends in  269,696.  */
/*operator * is multiplication. */
do j=2 by 2 /*start J at two, increment by two. */
if right(j*j, 6)==269696 then leave /*is six right-most digits our target? */
end /*this signifies the end of the DO loop*/
 
say "The smallest integer whose square ends in 269,696 is: " j

output

The smallest integer whose square ends in  269,696  is:  25264

examine remainder after dividing by 1 million[edit]

/*REXX program finds the  lowest (positive)  integer  whose  square  ends in  269,696.  */
/*operator // is division remainder.*/
do j=2 by 2 /*start J at two, increment by two. */
if j*j // 1000000 == 269696 then leave /*is square mod 1-million our target ? */
end /*this signifies the end of the DO loop*/
 
say "The smallest integer whose square ends in 269,696 is: " j

output   is identical as the 1st REXX version.

examine only numbers ending in 4 or 6[edit]

/*REXX program finds the  lowest (positive)  integer  whose  square  ends in  269,696.  */
/*we'll only examine integers that are */
/* ending in four or six. */
 
do j=4 by 10 /*start J at four, increment by ten.*/
k=j /*set K to J's value. */
if right(k*k, 6)==269696 then leave /*examine the right-most six digits. */
 
k=j+2 /*set K to J+2 value. */
if right(k*k, 6)==269696 then leave /*examine the right-most six digits. */
end /*this signifies the end of the DO loop*/
 
say "The smallest integer whose square ends in 269,696 is: " k

output   is identical as the 1st REXX version.

start with smallest possible number[edit]

/*REXX ----------------------------------------------------------------
* The solution must actually be larger than sqrt(269696)=519.585
*--------------------------------------------------------------------*/

z=0
Do i=524 By 10 Until z>0
If right(i*i,6)==269696 then z=i
Else Do
j=i+2
if right(j*j,6)==269696 then z=j
End
End
Say "The smallest integer whose square ends in 269696 is:" z
Say ' 'z'**2 =' z**2
Output:
The smallest integer whose square ends in 269696 is: 25264
                            25264**2 = 638269696

Ring[edit]

 
n = 0
while pow(n,2) % 1000000 != 269696
n = n + 1
end
 
see "The smallest number whose square ends in 269696 is : " + n + nl
see "Its square is : " + pow(n,2)
 

Output:

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

Ruby[edit]

n = 0
n = n + 2 until (n*n).modulo(1000000) == 269696
puts n
 

Run BASIC[edit]

for n = 1 to  1000000
if n^2 MOD 1000000 = 269696 then exit for
next
 
PRINT "The smallest number whose square ends in 269696 is "; n
PRINT "Its square is "; n^2
The smallest number whose square ends in 269696 is 25264
Its square is 638269696

Rust[edit]

 
fn main() {
let mut current = 0i32;
while (current * current)%1000000!=269696
{current+=1;
}
println!("The smallest number whose square ends in 269696 is {}",current);
}
 
Output:
The smallest number whose square ends in 269696 is 25264

Scala[edit]

//Babbage Problem
 
object babbage{
def main( args:Array[String] ){
 
var x:Int = 524 //Sqrt of 269696 = 519.something
 
while( (x*x) % 1000000 != 269696 ){
 
if( x%10 == 4 )
x = x+2
else
x = x+8
}
 
println("The smallest positive integer whose square ends in 269696 = " + x )
}
}
 

Scilab[edit]

Translation of: Pascal
n=2;
flag=%F
while ~flag
n = n+2;
if pmodulo(n*n,1000000)==269696 then
flag=%T;
end
end
disp(n);
Output:
   25264.

SequenceL[edit]

main() := babbage(0);
 
babbage(current) :=
current when current * current mod 1000000 = 269696
else
babbage(current + 1);
Output:
cmd:> babbage.exe
25264

Shen[edit]

(define babbage
N -> N where (= 269696 (shen.mod (* N N) 1000000)))
N -> (babbage (+ N 1))
 
(babbage 1)
Output:
25264

Sidef[edit]

var n = 0
while (n*n % 1000000 != 269696) {
n += 2
}
say n
Output:
25264

Smalltalk[edit]

"We use one variable, called n. Let it initially be equal to 1. Then keep increasing it by 1 for only as long as the remainder after dividing by a million is not equal to 269,696; finally, show the value of n."
| n |
n := 1.
[ n squared \\ 1000000 = 269696 ] whileFalse: [ n := n + 1 ].
n
Output:
25264

Swift[edit]

import Swift
 
for i in 2...Int.max {
if i * i % 1000000 == 269696 {
print(i, "is the smallest number that ends with 269696")
break
}
}
Output:
25264 is the smallest number that ends with 269696

Tcl[edit]

Hope Mr Babbage can understand this one-liner...

for {set i 1} {![string match *269696 [expr $i*$i]]} {incr i} {}
puts "$i squared is [expr $i*$i]"
25264 squared is 638269696

VBScript[edit]

'Sir, this is a script that could solve your problem.

'Lines that begin with the apostrophe are comments. The machine ignores them.

'The next line declares a variable n and sets it to 0. Note that the
'equals sign "assigns", not just "relates". So in here, this is more
'of a command, rather than just a mere proposition.
n = 0
 
'Starting from the initial value, which is 0, n is being incremented
'by 1 while its square, n * n (* means multiplication) does not have
'a modulo of 269696 when divided by one million. This means that the
'loop will stop when the smallest positive integer whose square ends
'in 269696 is found and stored in n. Before I forget, "<>" basically
'means "not equal to".
Do While ((n * n) Mod 1000000) <> 269696
n = n + 1 'Increment by 1.
Loop
 
'The function "WScript.Echo" displays the string to the monitor. The
'ampersand concatenates strings or variables to be displayed.
WScript.Echo("The smallest positive integer whose square ends in 269696 is " & n & ".")
WScript.Echo("Its square is " & n*n & ".")
 
'End of Program.
Output:
The smallest positive integer whose square ends in 269696 is 25264.
Its square is 638269696.

x86 Assembly[edit]

AT&T syntax
Works with: gas
# What is the lowest number whose square ends in 269,696?
 
# At the very end, when we have a result and we need to print it, we shall use for the purpose a program called PRINTF, which forms part of a library of similar utility programs that are provided for us. The codes given here will be needed at that point to tell PRINTF that we are asking it to print a decimal integer (as opposed to, for instance, text):
 
.data
decin: .string "%d\n\0"
 
# This marks the beginning of our program proper:
 
.text
.global main
 
main:
 
# We shall test numbers from 1 upwards to see whether their squares leave a remainder of 269,696 when divided by a million.
 
# We shall be making use of four machine 'registers', called EAX, EBX, ECX, and EDX. Each can hold one integer.
 
# Move the number 1,000,000 into EBX:
 
mov $1000000, %ebx
 
# The numbers we are testing will be stored in ECX. We start by moving a 1 there:
 
mov $1,  %ecx
 
# Now we need to test whether the number satisfies our requirements. We shall want the computer to come back and repeat this sequence of instructions for each successive integer until we have found the answer, so we put a label ('next') to which we can refer.
 
next:
 
# We move (in fact copy) the number stored in ECX into EAX, where we shall be able to perform some calculations upon it without disturbing the original:
 
mov  %ecx,  %eax
 
# Multiply the number in EAX by itself:
 
mul  %eax
 
# Divide the number in EAX (now the square of the number in ECX) by the number in EBX (one million). The quotient -- for which we have no use -- will be placed in EAX, and the remainder in EDX:
 
idiv  %ebx
 
# Compare the number in EDX with 269,696. If they are equal, jump ahead to the label 'done':
 
cmp $269696,  %edx
je done
 
# Otherwise, increment the number in ECX and jump back to the label 'next':
 
inc  %ecx
jmp next
 
# If we get to the label 'done', it means the answer is in ECX.
 
done:
 
# Put a reference to the codes for PRINTF into EAX:
 
lea decin,  %eax
 
# Now copy the number in ECX, which is our answer, into an area of temporary storage where PRINTF will expect to find it:
 
push  %ecx
 
# Do the same with EAX -- giving the code for 'decimal integer' -- and then call PRINTF to print the answer:
 
push  %eax
call printf
 
# The pieces of information we provided to PRINTF are still taking up some temporary storage. They are no longer needed, so make that space available again:
 
add $8,  %esp
 
# Place the number 0 in EAX -- a conventional way of indicating that the program has finished correctly -- and return control to whichever program called this one:
 
mov $0,  %eax
ret
 
# The end.
Output:
25264

XLISP[edit]

; The computer will evaluate expressions written in -- possibly nested -- parentheses, where the first symbol gives the operation and any subsequent symbols or numbers give the operands.
 
; For instance, (+ (+ 2 2) (- 7 5)) evaluates to 6.
 
; We define our problem as a function:
 
(define (try n)
 
; We are looking for a value of n that leaves 269,696 as the remainder when its square is divided by a million.
 
; The symbol * stands for multiplication.
 
(if (= (remainder (* n n) 1000000) 269696)
 
; If this condition is met, the function should give us the value of n:
 
n
 
; If not, it should try n+1:
 
(try (+ n 1))))
 
; We supply our function with 1 as an initial value to test, and ask the computer to print the final result.
 
(print (try 1))
Output:
25264

zkl[edit]

// The magic number is 269696, so, starting about its square root, 
// find the first integer that, when squared, its last six digits are the magic number.
// The last digits are found with modulo, represented here by the % symbol
const N=269696; [500..].filter1(fcn(n){ n*n%0d1_000_000 == N })
Output:
25264