partner8.rb

#!/usr/bin/ruby1.8
 
 
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 f1(n)
	n = n * 3 + 1 if (n.odd?)
	n /= 2 while (n.even?)
	return n
end

def widthdiff(x, y)
 
        x.to_s(2).length - y.to_s(2).length
 
end

def f(n)
 
	n1 = n
        c = 0
        m = 0
	
        while (n != 1 && n >= n1)
		n = f1(n)
                m = [m, n].max
                c += 1
        end
	
        return {'w' => widthdiff(m, n1), 
		'c' => c, 
		'd' => (0.5 - dense(n1)).abs,
		'm' => m}
 
end

def f2(n)
	
	a = f(n)
	ns = n.to_s(2)
	if (n == 1) then
		a['c2'] = 0
		return a
	end
	
	ns2 = ('1' + ns[2..-1])
	n2 = ns2.to_i(2)
	a2 = f(n2)
	a['c2'] = a['c'] - a2['c']
	a['2'] = a2
	return a
	
end

def long(m)
 
        l = [{'n' => 1, 'p' => 0}.merge(f2(1))]
 
	w = 'c2'
        loop \
        {
                l = l.sort_by { |x| [x[w], x['d']] }.reverse
 
                break if (l[0][w] >= m)
 
                x = l.delete_at(rand([l.size, 10].min))
 
                p2 = x['p'] + 1
                n2 = x['n'] + 2 ** p2
 
 
                x1 = x.dup
                x1['p'] = p2
                l << x1
 
                x2 = {'n' => n2, 'p' => p2}.merge(f2(n2))
                l << x2
		
		return if (l.size > 5000)
        }
 
        l = l.sort_by { |x| -x[w] }
        return l.first, l.size
end
 

def search(c)
	
	500.times \
	{
		|m|
		
		x, t = long(m)
		break if (x.nil?)
		
		ns = x['n'].to_s(2)
		puts([m, x['c2'] + c, c, t, ns.length, x.to_s].join("\t"))
		$stdout.flush
	}
	puts
	
end

10.times { |i| search(i); $stderr.puts(i) }