## Babbage’s Number

### October 9, 2018

This is simple:

```(define (babbage1)
(let loop ((n 1))
(if (= (modulo (* n n) 1000000) 269696) n
(loop (+ n 1)))))```

I won’t provide an example; you have to compute it yourself.

Our program runs so quickly it doesn’t seem worth the effort to optimize it, but you could make it faster by only testing numbers whose last digit is 4 or 6, in a manner similar to a prime wheel:

```(define (babbage2)
(let ((wheel (vector 2 8)))
(let loop ((n 4) (w 0))
(if (= (modulo (* n n) 1000000) 269696) n
(loop (+ n (vector-ref wheel w)) (- 1 w))))))
```

You can run the program at https://ideone.com/fKfXXe.

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