construct101c.rb

def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end

def seq(n)

	n1 = n
	l = [n1]
	while (n != 1)
		n = f2(n)
		l << n
	end 
	
	return l
end

def adj(ns)

	ns1 = ns.dup
	ns1[0, 1] = '10'
	
	ns2 = ns.dup
	ns2[0, 1] = '11'
	
	return ns1, ns2
end

def expand()
	l = [{'ns' => '1'}]

	20.times \
	{
		l2 = []
		l.each \
		{
			|x|
			adj(x['ns']).each \
			{
				|x|
				
				n = x.to_i(2)
				l1 = seq(n)
				cg = l1.index { |x| x < l1[0] }
				cg = l1.size if (cg.nil?)
				l2 << {'ns' => x, 'l' => l1, 'cg' => cg} if (cg >= x.length)
			}
		}
		l = l2
	}
	return l
end

def dense(w, d)
	w2 = w - 1
	
	a = (0...w2).to_a
	s = '0' * w2
	(1..(d * w - 1)).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' }
	return ('1' + s)
	
end


l = []
1e3.to_i.times \
{
	ns = dense(20, 0.5)
	l << {'l' => seq(ns.to_i(2))}
}

$stderr.puts(l.size)

a = {}
l.each_with_index \
{
	|x2, j|
	x2['l'].reverse.each_with_index \
	{
		|x, i|
		x1 = Math.log(x)
		x1 = x.to_s(2).length
		a[[i, x1]] = a.fetch([i, x1], 0) + 1
	}
}

a.sort_by { |k, v| v}.each { |k, v| puts([-k[0], k[1], Math.log(v)].join("\t")) }