grow3.rb

def f1(n)
        n = (n * 3 + 1) / 2 while (n % 2 == 1)
        n /= 2 while (n % 2 == 0)
        return n
end

def seq2(n)
	l = [n]
	n1 = n
	begin
		l << (n = f1(n))
	end while (n >= n1 && n != 1)
	return l
end

def d(s)
        c = s.split('').select { |x| x == '1' }.size
	d = s.empty? ? 0 : c.to_f / s.length
        return (0.5 - d).abs, d
        
end

def r(x)
	return sprintf("%.3f", x).to_f
end

def mnmx(l)
	return l.min, l.max
end

def stat(l)
        return 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 l.size, a, sd, l.max, l.min
end

def mx(n)
	l = seq2(n)
	d1, d = d(n.to_s(2))
	
	ls = l.size
	
	return {'ls' => ls, 'd' => d}
end

def three(n, p)


	p2 = p + 1
	n2 = n | (1 << p2)
	
	x = {'n' => n, 'p' =>p}.merge(mx(n))
	
	x2 = x.merge('p' => p2)
	x3 = {'n' => n2, 'p' => p2}.merge(mx(n2))
	
	return [x2, x3]
	
end

def hard(c)
		
	
	l1 = []
	l2 = three(1, 0)

	a = []
	c.times \
	{
		|n|
		$stderr.puts(n) if (n % 100 == 0)
		
		b = {}
		l2.each_with_index \
		{
			|x, i|
			ls = x['ls']
			b[ls] = b.fetch(ls, []) + [x.merge({'i' => i})]
		}
		
		j = (2..a.size).find { |i| a[i].nil? || a[i] < 20 }
		j = a.size if (j.nil?)
		
		k = b.keys.sort.find { |i| i >= j }
		k = b.keys.min if (k.nil?)
		x = b[k][rand(b[k].size)]
		i = x['i']
		
		x = l2.delete_at(i)
		l1 << x
		l2 += three(x['n'], x['p'])
		ls = x['ls']
		a[ls] = 0 if (a[ls].nil?)
		a[ls] += 1
#		p([j, k, b.keys.sort, a])
#		p(a)
	}
	
	return l1
	
end


l = hard(2000)

b = {}
l.each_with_index \
{
	|x, i|
	ls = x['ls']
	b[ls] = b.fetch(ls, []) + [x.merge({'i' => i})]
}
		
b.sort.each \
{
	|k, l|
	l1 = l.map { |x| x['d'] }
	puts([k, stat(l1)].join("\t"))
}