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

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

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: