extend17.rb

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

def f2(n)

	n = (n * 3 + 1) / 2 while (n.odd?)
	n /= 2 while (n.even?)
	return n

end

def stat(l)
        return 0, 0, 0, 0 if (l.empty?)
        t = t2 = 0
        l.each \
        {
		|x|
		t += x
		t2 += x ** 2
        }
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)

	return a, sd, l.max.to_f, l.min.to_f
end

def mono(l, z)

	return if (l.empty?)

	c = 0
        m = l[0]
	mx = nil
	j = 0
        l2 = []
        (1...l.size).each \
        { 
                |i| 
                c += 1 if (l[i] < l[i - 1])
                if (l[i] < m) then
                        l2 << i - j
                        m, j = [l[i], i] 
                end
                mx = [mx, i - j].compact.max
        }
	return if (c == 0 || mx.nil? || l2.empty?)
	
        r = c.to_f / l.size
	a, sd = stat(l2)
	
	return {'r' => r, 'mx' => mx, 'c' => l2.size, 
		'd' => l2.size.to_f / l.size, 'a' => a, 'sd' => sd
		}.merge(z)
end

def adv(x)

	n1 = n = x['n']
	ns = n.to_s(2)
	x['d'] = d(ns)
	l = [n]
	
	while (n >= n1 && n != 1)

		n = f2(n)
		l << n
	end
	
	x['c'] = l.size

	j = (0...l.size).max_by { |x| l[x] }
	
	z = mono(l[j..-1], {})
	
	x['mx'] = z.nil? ? 0 : z['mx']
	x['ns'] = ns.length
	x['ls'] = l.size
	x['lr'] = l.size - j
	
	x['by'] = [x['mx'], x['lr'], x['d']]
	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 out(a)
	puts(a.values_at(*$c).join("\t"))
	$stdout.flush
end

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

def add(l, z)

	l << next2(z[1])
	l << next2(z[2])
	
	out(z[1])
	
end

$c = ['ns', 'mx', 'ls', 'lr']
puts($c.join("\t"))

# test(); exit

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

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

	l = l.sort_by! { |x| x[1]['by'] }
	l.reverse!
	
	j = rand([l.size, 100].min)
	z = l.delete_at(j)
	
	add(l, z)
	
}