Source code in the unix programming language

# Program to determine the smallest positive integer whose square
# has a decimal representation ending in the digits 269,696.

# Start with the smallest positive integer of them all
let trial_value=1

# Compute the remainder when the square of the current trial value is divided
# by 1,000,000.␣
while (( trial_value * trial_value % 1000000 != 269696 )); do
  # As long as this value is not yet 269,696, increment
  # our trial integer and try again.
  let trial_value=trial_value+1
done

# To get here we must have found an integer whose square meets the
# condition; display that final result
echo $trial_value

#!/bin/dash				

#  Babbage problem:
#  	What is the smallest (positive) integer whose square ends in the digits 269,696?  
#
#  He found the second to smallest number (99736 instead of 25264) using pencil and paper,
#  and would not have wasted hours of computing time on his (planned) Analytical Engine (AE).
#
#  As most human computers know, a square must end in 0, 1, 4, 5, 6 or 9.
#  because the squares of 0 to 9 end in 0, 1, 4, 9, 6, 5, 6, 9, 4, 1.
#  Thus, the result must have the last digits 14 or 16 in the above case.
#
#  So the algorithm starts with the set {0} and an increment of 1,
#  squaring all numbers of 0+i, and keeping only those that have 
#  the correct end digit.
#  Then, the new i is 10*i, and a new set of two digit endings
#  created from the old set of one digit endings, and so on.
#
#  As the AE did not have arrays or the like, the sets must be punched
#  on cards and read in for the next round. 
#  The classical (original) Bourne Shell did not have arrays,
#  so you may use this script on very old machines, if 'expr' is used
#  instead of arithmetic expansion. 
#  And so his script works with 'dash', the standard command interpreter
#  for non-interactive use.
#
#  To prove the speed, try 1234554321 instead of 269696,
#  the practicall immedidate answer should be 1250061111,
#  while the simple method will take hours.  
#
#  Note that this method will stop if there is no solution,
#  while the simple method continues endlessly.

# filename for workfile(s)
wrk=$(basename $0 .sh).data

# set $e to desired ending. Leading zeroes are ignored.
e=${1:-269696}

# set the modulus $m to the power of 10 above $e
m=1
while test $m -le $e
do m=$((m*10))
done
 
# $a is number to add in each round (power of 10)
a=1
 
# first workfile contains just the number 0 
echo 0 >$wrk	
 
# test all workfile numbers with another digit in front
while test $a -lt $m		# until the increment excees the modulus
do mm=$((a*10))			# modulus in this round
   ee=$((e % mm))		# ending in this round
   cat $wrk |			# numbers from current workfile
      while read x
      do y=$x			# first number to test is the number read
	 while test $y -le $((x+mm-1))		
	 do z=$(($y * $y))	# calculate the square
	    z=$(($z % $mm))	# ending in this round
	    if test $z -eq $ee	
	    then echo $y	# candidate for next round
	    fi
	    y=$(($y + $a))	# advance leftmost digit
	 done
      done  >$wrk.new		# create new workfile
   # next round
   a=$((a*10))			# another leftmost digit
   mv $wrk.new $wrk		# cycle workfiles
done

# find each number in the last workfile  if x*x mod m = e
# ending in $e and modulus in $m
cat $wrk |			# numbers from last workfile
   while read x
   do y=$(($x * $x))		# check
      y=$(($y % $m))
      if test $y -eq $e
      then echo $x		# solution found
      fi
   done | 
   sort -n |    		# numbers in ascending order
   head -n 1 			# show only smallest