end.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 f1(n)
	n = n * 3 + 1 if (n.odd?)
	n /= 2 while (n.even?)
	return n
end

def f(n)
 
	n1 = n
        c = 0
        m = 0
	
        while (n != 1 && n >= n1)
		n = f1(n)
                m = [m, n].max
                c += 1
        end
	
        return {'w' => widthdiff(m, n1), 
		'c' => c, 
		'd' => (0.5 - dense(n1)).abs,
		'm' => m}
 
end
 
def long(m)
 
        l = [{'n' => 1, 'p' => 0}.merge(f(1))]
 
	w = 'w'
        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(x, y)
 
        x.to_s(2).length - y.to_s(2).length
 
end
 
x, c = long(ARGV[0].to_i)
	
n = x['n']

while (n != 1)
	n2 = n
	n = f1(n)
	ns = n.to_s(2)
	l0 = ns.split(/0+/)
	l1 = ns.split(/1+/)
	m0 = l0.map { |x| x.length }.max
	m1 = l1.map { |x| x.length }.max
	m1 = 0 if (m1.nil?)
	puts([ns.length, l0[-1].length, m0, m1].join("\t"))
end