long18b.rb

def stat(l)
        return 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)
        raise if (sd.nan?)
        return a, sd
end
   
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 f(n)

	n1 = n
	c = 0
	while (n != 1 && n >= n1)
		n = n * 3 + 1 if (n.odd?)
		n /= 2 while (n.even?)
		c += 1
	end
	return {'c' => c, 'd' => (0.5 - dense(n1)).abs}

end

def match(n1, n2)
	
	i = 0
	i += 1 while (i < n1.size && i < n2.size && n1[i, 1] == n2[i, 1])
	return i
end

def f2(n)
	
	n2 = n

	while (n != 1)

		n = n * 3 + 1 if (n.odd?)
		n /= 2 while (n.even?)
		
		n2 = n2 * 3
		ns = n.to_s(2)
		n2s = n2.to_s(2)
		puts([match(ns, n2s), ns.length].join("\t"))
	#	p([n.to_s(2), n2.to_s(2)])

	end

end


def long(m)
	
	l = [{'n' => 1, 'p' => 0}.merge(f(1))]
	t = 0

	loop \
	{
		l = l.sort_by { |x| [x['c'], -x['d']] }.reverse

		x = l.delete_at(rand([l.size, 2].min))

		p2 = x['p'] + 1
		n2 = x['n'] + 2 ** p2
		
		
		x1 = x.dup
		x1['p'] = p2
		l << x1
		
		x2 = {'n' => n2, 'p' => p2}.merge(f(n2))
		l << x2
		t += 1

		break if (t >= m)
	}

	l.sort_by! { |x| -x['c'] }
	$stderr.puts(l[0]['c'])
	return l[0]['n']
end

n = long(500)

f2(n)