long25.rb

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.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}

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, 2].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.sort_by! { |x| -x['c'] }
	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
	
	mx = ma = mb = 0
	m = nil
	
	while (b != 1 && b >= b1)
		
		a = a * 3 + 1 if (a.odd?)
		a /= 2 while (a.even?)
		
		b = b * 3 + 1 if (b.odd?)
		b /= 2 while (b.even?)

		m = widthdiff(a, b).abs
		
		mx = [m, mx].max
		ma = [a, ma].max
		mb = [b, mb].max
	end


	return mx, widthdiff(ma, a1), widthdiff(mb, b1), c

end

(1..1000).each \
{
	|p|
	puts([p, two(p)].join("\t"))
	$stdout.flush
}