[QUIZ SOLUTION] Happy Numbers (#93) - happy bases

Discussion in 'Ruby' started by Daniel Martin, Sep 6, 2006.

  1. Here's my solution to find happy bases - note that I don't find any
    happy bases (aside from 2 and 4) before I run out of memory, somewhere
    near base 1700. It wouldn't surprise me if no other happy bases
    exist.

    The program checks up to 2*(base-1)*(base-1) for numbers that fall
    into an infinite loop (that is not '1' forever) when applying the
    digit-square-sum function. This is all that's needed, as it can
    easily be shown that any number will eventually get less than that.

    There's almost certainly some stuff I could do to be more parsimonious
    with memory, chief among them finding a copy of narray that has the
    mod! method. (I may revisit this and use a combination of div!, mul!
    and sbt! to cut down on temporary arrays) However, this program as it
    stands very quickly checks much farther out than I would have thought
    necessary if there really were other happy bases out there to be
    found.

    #!/usr/bin/env ruby
    require 'narray'

    def dodigsum(base, initial)
    tmp = initial / (base ** NArray.to_na([[0],[1],[2]]))
    # I would use mod!, but my copy of narray doesn't have mod!
    tmp = tmp % base
    tmp.mul!(tmp)
    initial.fill!(0).add!(tmp.sum(1))
    end

    def checkbase(base = 10)
    base = base.to_i
    checklimit = 2*(base-1)*(base-1)
    check = NArray.int(checklimit + 1).indgen!
    check_initial = check.dup

    while true do
    dodigsum(base,check)
    if check.eq(check_initial).count_true > 2
    #Gobs of debugging info
    # lp = check.mul!(check.eq(check_initial)).mask(check.ge(2)).min
    # puts "#{base} has a loop on #{lp}"
    break
    end
    if check.le(1).count_true > checklimit
    puts "#{base} is a happy base"
    break
    end
    end
    end

    2.upto(3000) { |b|
    begin
    checkbase(b)
    rescue Interrupt
    puts "Checking #{b}"
    checkbase(b)
    rescue Error => e
    puts "Bailing on #{b}"
    raise e
    end
    }

    __END__


    --
    s=%q( Daniel Martin --
    puts "s=%q(#{s})",s.map{|i|i}[1] )
    puts "s=%q(#{s})",s.map{|i|i}[1]
     
    Daniel Martin, Sep 6, 2006
    #1
    1. Advertising

  2. Re: [QUIZ SOLUTION] Happy Numbers (#93) - find the happiest

    And here's my narray-based solution to find the happiest number under
    1_000_000 - it's not the shortest solution I've seen, but it's pretty
    fast. It eliminates numbers that end up in loops by setting all
    looping numbers to 0.

    #!/usr/bin/env ruby
    require 'narray'

    def dodigsum(initial, base)
    ndigits = (Math.log(initial.max)/Math.log(base)).ceil
    tmp = initial / (base ** NArray.to_na((0...ndigits).map{|x|[x]}))
    tmp = tmp % base
    tmp.mul!(tmp)
    initial.fill!(0).add!(tmp.sum(1))
    end

    limit = ARGV[0] || 1_000_000
    base = ARGV[1] || 10

    limit = limit.to_i
    base = base.to_i

    check = NArray.int(limit + 1).indgen!
    check_initial = check.dup
    check_initial[1] = 0
    dodigsum(check, base)
    checkp = check.dup

    onemask = check.eq(1)
    # onemask now contains the location of "0 order" happy numbers
    order = 0
    found_ex = nil
    while (check.ge(2).count_true > 0) do
    check.mul!(check.ne(check_initial))
    check = check[checkp]
    newmask = check.eq(1)
    order = order + 1
    if (not newmask == onemask)
    found_ex = [newmask.gt(onemask).where.min, order]
    end
    onemask = newmask
    end
    puts "Happiest is #{found_ex[0]}, with happiness order #{found_ex[1]}"
    __END__


    --
    s=%q( Daniel Martin --
    puts "s=%q(#{s})",s.map{|i|i}[1] )
    puts "s=%q(#{s})",s.map{|i|i}[1]
     
    Daniel Martin, Sep 6, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. email55555 email55555

    [SOLUTION] Ruby Quiz #14 LCD Numbers ( solution #2 )

    email55555 email55555, Jan 9, 2005, in forum: Ruby
    Replies:
    16
    Views:
    296
    David Tran
    Jan 10, 2005
  2. David Tran
    Replies:
    9
    Views:
    217
    David Tran
    Jan 21, 2005
  3. Ruby Quiz

    [QUIZ] Happy Numbers (#93)

    Ruby Quiz, Sep 1, 2006, in forum: Ruby
    Replies:
    45
    Views:
    788
    Matthew Moss
    Sep 7, 2006
  4. Glen F. Pankow

    [QUIZ SOLUTION] Happy Numbers (#93)

    Glen F. Pankow, Sep 6, 2006, in forum: Ruby
    Replies:
    3
    Views:
    254
    James Edward Gray II
    Sep 6, 2006
  5. Rick DeNatale

    [QUIZ SOLUTION] Happy Numbers (#93)

    Rick DeNatale, Sep 6, 2006, in forum: Ruby
    Replies:
    0
    Views:
    103
    Rick DeNatale
    Sep 6, 2006
Loading...

Share This Page