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.

Pages: 1 2

7 Responses to “Babbage’s Number”

1. V said

Ruby one-liner.

```  p (1..Float::INFINITY).find { |i| (i * i).to_s =~ /269696\$/ }
```
2. Steve said

GTM>w 269696**.5 ; Square root of 269696
; 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

3. Klong version

```{[l]; l::[]; {:["269696"=(-6)#\$(x*x); l::l,x; ""]}'1+!99740; l}()
```

Examples:
[25264 99736]

4. Milbrae said

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

5. Steve said

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]

6. Daniel said

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:

```25264
99736
150264
224736
275264
349736
400264
474736
525264
599736
650264
724736
775264
849736
...
```
7. matthew said

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:
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

c = chr(ord('0')+d) if d<10 else chr(ord('a')-10+d)
if n == 0: return c

if s:
m = s[0]

```

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

```n=269696,radix=5: [119014, 271611]
n: 32112241 m*m: 213002032112241
n: 2202200 m*m: 402202200
n: 269696 m*m: 638269696
n: 174699 m*m: 62926174699
n: 70400 m*m: c270400