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