extend12.rb

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

def seq(n)

	n1 = n
	ns = n.to_s(2)
	s = ''

	while (n >= n1 && n != 1)

		while (n.odd?)
			n = (n * 3 + 1) / 2 
			s << '1'
		end
			
		while (n.even?)
			n /= 2 
			s << '0'
		end
		
	end
	
	return s

end

def prefix(s1, s2)
	
	i = 0
	i += 1 while (i < s1.length && i < s2.length && s1[i, 1] == s2[i, 1])
	return i
end

def extra(n)
		ns = n.to_s(2)
		nslo = ns[2..-1]
		ns2 = '1' + (nslo.nil? ? '' : nslo)
		s1 = seq(n)
		s2 = seq(ns2.to_i(2))
		j = prefix(s1, s2)
#		p([ns.length, s1.length, s2.length, j, s1.length - j])
		return s1.length - j
end

def adv(x)
	n = x['n']
	x['d'] = d(n.to_s(2))
	x['z'] = extra(n)
	return x
end

def next2(z)
	
	l = [z]
	p = z['p'] + 1
	
	l << adv({'n'=>z['n'] + 2**p, 'p'=>p})
	l << z.merge({'p'=>p})
	return l
end

def test()
	
	l = File.open('db.txt').readlines.map { |x| Kernel.eval(x) }
	l.each \
	{
		|x|
		p(extra(x['n']))
	}
end


# test(); exit

l = [next2({'n'=>1, 'p'=>0})]

20000.times \
{
	|i|
	$stderr.puts(i) if (i % 100 == 0)

	l = l.sort_by! { |x| [x[1]['z'], x[1]['d']] }
	l.reverse!
	
	j = rand([l.size, 20].min)
	z = l.delete_at(j)
	
	l << next2(z[1])
	l << next2(z[2])
	
	puts([l.size, z[1]['z'], z[1].inspect].join("\t"))
	$stdout.flush
}