mix.rb

def f2(n)
	return n.odd? ? (n * 3 + 1) / 2 : n / 2

end

def dense(w, d)
	w2 = w - 1
	
	a = (0...w2).to_a
	s = '0' * w2
	(1..(d * w - 1)).map { a.delete_at(rand(a.size)) }.each { |x| s[x, 1] = '1' }
	return ('1' + s).to_i(2) 
	
end

def stat(l)
	l = [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 stat2(l, t, n)
	return Hash[[["a#{n}", "sd#{n}", "mx#{n}"], stat(l)[0..2]].transpose]
end

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

def data(n)
	
	$seen = {'h' => 0} if ($seen.nil?)
	seen = $seen
	
	if (seen.member?(n)) then
		seen['h'] += 1
		$stderr.puts("h #{seen['h']} ss #{seen.size}") if (seen['h'] % 1000 == 0)
		return seen[n]
	end


	ns = n.to_s(2)
	nl = ns.length
	m = nl / 2
	
	nsh = ns[0..m]
	nsl = ns[m..-1]
	
	asdm1 = stat2(ns.split(/0+/).map { |x| x.length }, nl, 1)
	
	l1 = ns.split(/1+/)
	
	l1.shift
	asdm0 = stat2(l1.map { |x| x.length }, nl, 0)
	
	x = {'n' => n, 'ns' => ns, 'nl' => nl, 'd' => d(ns), 'dh' => d(nsh), 'dl' => d(nsl)}.merge(asdm1).merge(asdm0)
	seen[n] = x if (seen.size < 100e3)
	return x
end

def count(z)
	
	n = z['n']
	n1 = n
	l = []
	mmx0 = 0
	mmx1 = 0
	begin
		x = data(n)
		mmx0, mmx1 = [[mmx0, x['mx0']].max, [mmx1, x['mx1']].max]
		l << n
		n = f2(n) 
	end while n > n1
	
		
	m = (0...l.size).max_by { |x| l[x] }
	r = l[m].to_s(2).length - n1.to_s(2).length
	
	return z.merge({'c' => l.size, 'n' => n1, 'l' => l, 'm' => m, 'r' => r, 'mmx0' => mmx0, 'mmx1' => mmx1, 'mmx' => [mmx0, mmx1].max})
end

def next2(z)
	
	p = z['p'] + 1
	return [z, count({'n'=>z['n'] + 2 ** p, 'p'=>p}), z.merge({'p'=>p})]
end


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

	a = nil
	mx = nil
	500.times \
	{
		|j|
		$stderr.puts("j #{j} #{a}") if (j % 100 == 0)
		l1 = (0...l.size).select { |x| l[x][1]['mmx'] <= m }.sort_by { |x| -l[x][1]['c'] }

		break if (l1.empty?)
		a = l[l1[0]][1].select { |k, | k != 'l'}
		
		mx = [mx, a['mmx']].compact.max
		
		i = l1[rand([l1.size, 20].min)]
		z = l.delete_at(i)

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

	}
	return a.merge({ 'mx' => mx, 'm' => m })
end

def out(fn, a)
	
	f = File.open(fn, 'a')
	f.puts(a.keys.join("\t")) if (f.size == 0)
	f.puts(a.values.join("\t"))
	f.close
end

f = File.open('gnuplot.cmd', 'w')

f.puts <<eof
set colors classic; set y2tics; set ytics nomirror; set y2range [0:]; plot [][0:] 'out.txt' using (column('m')) with line lw 2,'' using (column('mmx')) with line,\\
'' using (column('c')) with line lw 3 axes x1y2
eof

f.close

File.open(fn = 'out.txt', 'w').close

25.downto(4) \
{
	|m|
	4.times { a = limit(m); out(fn, a) }
}