end7.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) / 2 while (n.odd?)
		n /= 2 while (n.even?)
		
                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
		raise if (l.size >= 1000)
        }
 
        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

def run()
	
	x, c = long(ARGV[0].to_i)
	
	n = x['n']
	
	l = []

	while (n != 1)
		
		c1 = c0 = 0
		while (n.odd?)
			n = (n * 3 + 1) / 2
			c1 += 1
		end
		while (n.even?)
			n /= 2 
			c0 += 1
		end
		
		ns = n.to_s(2)

		puts([ns.length, c0, c1].join("\t"))

	end

	
end

run()