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.

Advertisements

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

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

    n=269696,radix=5: [119014, 271611]
     n: 32112241 m*m: 213002032112241
    n=269696,radix=7: [4830, 112819, ...]
     n: 2202200 m*m: 402202200
    n=269696,radix=10: [25264, 99736, ...]
     n: 269696 m*m: 638269696
    n=269696,radix=11: [402889, 1368672]
     n: 174699 m*m: 62926174699
    n=269696,radix=14: [9576, 9632, ...]
     n: 70400 m*m: c270400
    n=269696,radix=17: [362571, 1057286]
     n: 33f38 m*m: 11e6333f38
    n=269696,radix=22: [80264, 1208144, ...]
     n: 1374k m*m: 2ci1374k
    n=269696,radix=25: [119014, 271611]
     n: h6cl m*m: 280ah6cl
    n=269696,radix=29: [241391, 465890]
     n: b1jp m*m: 3arpb1jp
    n=269696,radix=34: [112008, 222076, ...]
     n: 6ta8 m*m: 8446ta8
    n=269696,radix=35: [7861, 66514, ...]
     n: 6a5l m*m: 166a5l
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: