grow11.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
	l << (n = f1(n)) 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
	
	cm = (0...l.size).max_by { |x| l[x] }
	return {'ls' => ls, 'd' => d, 'cm' => cm}
end

def three(x)

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

def hard(c)
		
	
	x = {'n' => 1, 'p' => 0}.merge(mx(1))
	b = {}
	t = {}
	tt = {}
	mx = {}
	
	a = []
	t1 = Time.now.to_i
	c.times \
	{
		|n|
		$stderr.printf("%i %.1fm\n", n, (Time.now.to_i - t1).to_f / 60) if (n % 1000 == 0)
		
		cm = x['cm']
		t[cm] = t.fetch(cm, 0) + 1
		
		if (mx[cm].nil? || x['d'] > mx[cm]) then
			mx[cm] = x['d']
			tt[cm] = tt.fetch(cm, 0) + 1
		end
		
		a[cm] = 0 if (a[cm].nil?)
		a[cm] += 1
		
		three(x).each \
		{
			|x2|
			cm = x2['cm']
			b[cm] = b.fetch(cm, []) + [x2]
		}

		k = (b.keys - t.keys).min # max
		
		k = (b.keys & t.keys).max_by { |x| tt[x].to_f / t[x] } if (k.nil?)
#		k = b.keys[rand(b.size)]

		x = b[k].delete_at(rand(b[k].size))
		b.delete(k) if (b[k].empty?)
		
	}
	
	f = File.open('grow.txt', 'w')
	b.sort.each \
	{
		|k, l|
		l1 = l.map { |x| x['d'] }
		puts([k, tt[k], stat(l1)].join("\t"))
		f.puts(l.inspect)
	}
	
end


hard(100000)