def f1(n)
        n = (n * 3 + 1) / 2 while (n % 2 == 1)
        n /= 2 while (n % 2 == 0)
        return n
end

def seq2(n)
	l = [n]
	n1 = n
	begin
		l << (n = f1(n))
	end while (n >= n1 && n != 1)
	return l
end

def d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = c.to_f / s.length
        return (0.5 - d).abs

end

def r(x)
	return sprintf("%.3f", x).to_f
end

def mx(n)
	l = seq2(n)

	d = d(n.to_s)

	mx = l.max
	m = mx.to_s(2).length.to_f / n.to_s(2).length
	return {'by' => [-m, d], 'm' => m, 'ls' => l.size}
end

def hard(c)


	l = [{'n' => 1, 'p' =>0}.merge(mx(1))]

	loop \
	{
		l.sort_by! { |x| x['by'] }

		return l[l.size / 2] if (l.size == c)

		x = l.delete_at(rand([l.size, 100].min))


		p = x['p'] + 1
		n = x['n']

		x1 = x.dup
		x1['p'] = p
		l.push(x1)

		x2 = {}
		n |= (1 << p)

		x2['n'] = n
		x2['p'] = p
		x2.merge!(mx(n))
		l.push(x2)

		puts([l.size, r(x2['m']), x2['n'].to_s(2).length, x2['ls']].join("\t"))
		$stdout.flush
	}


end

z = hard(10000)