limit5.rb

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
	ns = n.to_s(2).length
	
	v = mx.to_s(2).length.to_f / ns
	h =  l.size.to_f / ns
	
	return {'by' => [-(v * h), d], 'ns' => ns, 'ls' => l.size, 
		'v' => r(v), 'h' => r(l.size.to_f / ns)}
end

def fmt(x)
	
	x = x.dup
	['n', 'p', 'by'].each { |k| x.delete(k) }
	return x.to_a
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] + fmt(x2)).join("\t"))
		$stdout.flush
	}
	
	
end

z = hard(10000)