Babbage’s Number
October 9, 2018
Charles Babbage, whose Analytical Engine was a direct predecessor of today’s digital computer, gave this example of a problem that his Analytical Engine could solve in an 1837 letter to Lord Bowden:
What is the smallest positive integer whose square ends in the digits 269,696?
Babbage knew that 99,736 has a square with the required ending, but didn’t know if there was a smaller number.
Your task is to find Babbages’s number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Ruby one-liner.
p (1..Float::INFINITY).find { |i| (i * i).to_s =~ /269696$/ }GTM>w 269696**.5 ; Square root of 269696
519.322635747759401 ; So start with 520.
; Only squares ending in 6 come from numbers ending in 4 or 6.
GTM>f i=520:10:1000000 f j=4,6 s k=i+j,sq=k*k i $e(sq,$l(sq)-5,$l(sq))=269696 w !,k
25264 <– Smallest
99736
150264
224736
275264
349736
400264
474736
525264
599736
650264
724736
775264
849736
900264
974736
Klong version
{[l]; l::[]; {:["269696"=(-6)#$(x*x); l::l,x; ""]}'1+!99740; l}()Examples:
[25264 99736]
Python
import math N = 269696 M = 10**6 Q = 520 # square root of N, rounded to the nearest even int for v in range (Q, M, 2): if pow(v, 2, M) == N: print (v)25264
99736
150264
224736
275264
349736
400264
474736
525264
599736
650264
724736
775264
849736
900264
974736
Faster Klong version only searching for numbers ending in 4 or 6
test2::{[l]; l::[]; {[a]; a::x*10; {[b]; b::a+x; :["269696"=(-6)#$(b*b); l::l,b;""]}'[4 6]}'1+!9974;l}Run:
test2()
[25264 99736]
Here’s a solution in Python. The generators yield positive integers whose squares end in 269,696.
from itertools import count, cycle def babbage_numbers1(): for x in count(1): if str((x**2)).endswith("269696"): yield x def babbage_numbers2(): for x in count(0, 10): for y in (4, 6): if str((x+y)**2).endswith("269696"): yield x+y def babbage_numbers3(): x = 25264 for y in cycle((74472, 50528)): yield x x += y for x, y, z in zip(babbage_numbers1(), babbage_numbers2(), babbage_numbers3()): assert x == y == z print(x)Output:
Generalizing the “must end in 4 or 6” argument, we can build up the list of “square roots” digit by digit. It’s also easy to generalize to any radix:
def msqrt(n,radix=10): """ Find all m where m*m ends in the same digits as n ie. all m < k where m*m%k == n%k where k is smallest power of radix greater than n. """ k,s = 1,[0] # if abcd**2 = ..WXYZ, then bcd**2 = ...XYZ while k <= n: k0,k = k,radix*k s = [m for i in range(radix) for j in s for m in [i*k0+j] if m*m%k == n%k] #assert(s == [m for m in range(0,k) if m*m%k == n%k]) return s def int2string(n,radix): assert(radix <= 36) n,d = divmod(n,radix) c = chr(ord('0')+d) if d<10 else chr(ord('a')-10+d) if n == 0: return c return int2string(n,radix) + c def test(n,radix=10): s = msqrt(n,radix) if s: print("n=%s,radix=%s: %s"%(n,radix,s)) m = s[0] print(" n: %s m*m: %s"%(int2string(n,radix),int2string(m*m,radix))) for radix in range(2,37): test(269696,radix)So it’s nice to know that 269696 is b1jp in radix-29, and 241391 squared is 3arpb1jp: