long25b.rb

#!/usr/bin/ruby1.8
 
 
def dense(n)
 
        s = n.to_s(2)
        c = 0
        s.length.times \
        {
                |i|
                c += s[i, 1].to_i
        }
        return c.to_f / s.length
 
end
 
def f(n)
 
        n1 = n
        c = 0
        m = 0
        while (n != 1 && n >= n1)
                n = n * 3 + 1 if (n % 2 == 1)
                n /= 2 while (n % 2 == 0)
                m = [m, n].max
                c += 1
        end
        return {'w' => widthdiff(m, n1), 'c' => c, 'd' => (0.5 - dense(n1)).abs}
 
end
 
def long(m)
 
        l = [{'n' => 1, 'p' => 0}.merge(f(1))]
 
        loop \
        {
                l = l.sort_by { |x| [x['w'], x['d']] }.reverse
 
                break if (l[0]['w'] >= m)
 
                x = l.delete_at(rand([l.size, 10].min))
 
                p2 = x['p'] + 1
                n2 = x['n'] + 2 ** p2
 
 
                x1 = x.dup
                x1['p'] = p2
                l << x1
 
                x2 = {'n' => n2, 'p' => p2}.merge(f(n2))
                l << x2
        }
 
        l = l.sort_by { |x| -x['w'] }
        return l.first, l.size
end
 
def widthdiff(a, b)
 
        a.to_s(2).length - b.to_s(2).length
 
end
 
def two(p)
 
        x, c = long(p)
        a = x['n']
 
        a1 = a
 
        ns = a.to_s(2)
 
        b = ('1' + ns[2..-1]).to_i(2)
        b1 = b
 
        ma = mb = 0
 
        while (b != 1 && b >= b1)
 
                a = a * 3 + 1 if (a % 2 == 1)
                a /= 2 while (a % 2 == 0)
 
                b = b * 3 + 1 if (b % 2 == 1)
                b /= 2 while (b % 2 == 0)
 
                ma = [a, ma].max
                mb = [b, mb].max
        end
 
 
        return widthdiff(ma, mb), widthdiff(ma, a1), widthdiff(mb, b1), c
 
end
 
(1..1000).each \
{
        |p|
        puts([p, two(p), Time.now].join("\t"))
        $stdout.flush
}