85 lines
2.8 KiB
Bash
85 lines
2.8 KiB
Bash
#!/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
|