## 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.

Ruby one-liner.

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

Examples:

[25264 99736]

Python

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

Run:

test2()

[25264 99736]

Here’s a solution in Python. The generators yield positive integers whose squares end in 269,696.

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:

So it’s nice to know that 269696 is b1jp in radix-29, and 241391 squared is 3arpb1jp: