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.

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: