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

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

end


def widthdiff(x, y)
	x.to_s(2).length - y.to_s(2).length
end

def widthratio(x, y)
	x.to_s(2).length.to_f / y.to_s(2).length
end

def widthratio100(x, y)
	(widthratio(x, y) * 100).to_i
end

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

end

def count(x)
	n = n1 = x['n']
	l = [n]
	cg = nil
	while (n != 1)
		n = f1(n)
		cg = l.size if (cg.nil? && n < n1)
		l << n
	end
	cm = (0...l.size).max_by { |x| l[x] }
	return x.merge!({'cm' => cm,
		'cg' => cg.nil? ? 0 : cg,
		'm' => l[cm].to_s(2).length,
		'w' => widthdiff(l[cm], n1),
		'r' => widthratio(l[cm], n1),
		'c' => l.size,
		'd' => (0.5 - d(n1.to_s(2))).abs,
		'l' => l,
		'nl' => n1.to_s(2).length})
end


def count2(z)

	n = z['n']
	n1 = n
	l = [n]
	begin
		n = f2(n)
		l << n
	end while (n > n1)

	cm2 = (0...l.size).max_by { |x| l[x] }
	w2 = widthdiff(l[cm2], n1)
	v2 = widthratio100(l[cm2], n1)

	return z.merge({'c2' => l.size,
		'cm2' => cm2,
		'w2' => w2,
		'v2' => v2,
		'd' => (0.5 - d(n1.to_s(2))).abs})
end

def next2(z)

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


def hard(c)

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

	a = nil

	c.times \
	{
		|j|
		l1 = (0...l.size).sort_by { |x| [-l[x][1][k], l[x][1]['d']] }

		a = l[l1[0]][1].select { |k, | k != 'l'}
		$stderr.puts("j #{j} #{a}") if (j % 100 == 0)

		i = l1[rand([l1.size, 20].min)]
		z = l.delete_at(i)

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

	}
	return l.map { |x| x[0] }
	return a
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, c.to_f
end

def stat2(l, t, n)
	l1 = stat(l)

	return Hash[[["a#{n}", "sd#{n}", "mx#{n}", "c#{n}",
		"a#{n}s", "sd#{n}s", "mx#{n}s", "c#{n}s"],
		l1 + l1.map { |x| x / t }].transpose]
end

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

end

def data(z)

	n = z['n']
	$seen = {'h' => 0} if ($seen.nil?)
	seen = $seen

	if (seen.member?(n)) then
		seen['h'] += 1
		$stderr.puts("\t\th #{seen['h']} ss #{seen.size}") if (seen['h'] % 10000 == 0)
		return z.merge(seen[n])
	end


	ns = n.to_s(2)
	nl = ns.length
	m = nl / 2

	nsh = ns[0..m]
	nsl = ns[m..-1]

	asdm1 = stat2(l1 = ns.split(/0+/).map { |x| x.length }, nl, 1)
	asdm0 = stat2(l0 = [ns.split(/1+/)[1..-1]].compact.flatten.map { |x| x.length }, nl, 0)


	x = {'n' => n, 'ns' => ns, 'nl' => nl, 'd' => (d = d(ns) - 0.5),
		'dc' => d.abs, 'e' => 1.0 - (l1.length + l0.length).to_f / nl,
		'dh' => d(nsh) - 0.5, 'dl' => d(nsl) - 0.5}.merge(asdm1).merge(asdm0)
	seen[n] = x if (seen.size < 100e3)
	return z.merge(x)
end

def subglides(l)

	return l.map \
	{
		|x|
		l1 = x['l']
		l2 = (0...l1.size).map \
		{
			|i|
			j = i
			j += 1 while (j < l1.size - 2 && l1[j] >= l1[i])
			{'n' => l1[i], 'cg' => j - i, 'nl' => l1[i].to_s(2).length}
		}.select { |x| x['nl'] > 20 && x['cg'] >= 5}
	}.flatten

end

def sample(a, b)

	l = []
	a.times { l.concat(hard(b)) }

	l = subglides(l)

	seen = {}
	c1 = l.size
	l.each { |x| seen[x['n']] = x }

	$stderr.puts({'c1' => c1, 'c2' => l.size})
	l = seen.values

	c = {}
	l.each { |x| c[x['nl']] = [] if (!c.member?(x['nl'])); c[x['nl']] << x }
	x = c.max_by { |k, v| v.size }
	$stderr.puts({'nl' => x[0], 'c' => x[1].size}.inspect)
	return x[1]

end

def linear(l, f, mn, mx, k)

	c = (l.size * (1.0 / f)).to_i

	raise ({'c1' => c, 'c2'=> l.size, 'f' => f}.inspect) if (c <= 1)

	return if (c > l.size)

	l1 = (0...l.size).to_a

	r = mx - mn
	tm = nil
	l0 = []
	c.times \
	{
		|i|

		t = mn + (i.to_f / (c - 1)) * r

		l2 = (0...l1.size).map { |x| [x, (l[l1[x]][k] - t).abs / r] }
		i, t1 = l2.min_by { |x| x[1] }
		t2 = t1 * (c - 1)
		tm = [tm, t2].compact.max
		break if (t2 > 1.0)

		l0 << l1.delete_at(i)

	}
	$stderr.puts({'c' => c, 'f'=> f.to_i, 'tm' => tm.round(3)}.inspect)
	return if (l0.size != c)
	return l.values_at(*l0)

end



def resample(l, k)

	mn = l.min_by { |x| x[k] }[k]
	mx = l.max_by { |x| x[k] }[k]

	mn2 = (1.0 * mn).to_i
	mx2 = (1.0 * mx).to_i

	$stderr.puts([k, 'ls', l.size, 'mn', mn, 'mn2', mn2, 'mx', mx, 'mx2', mx2].inspect)

	f = 10
	l1 = linear(l, f, mn2, mx2, k)

	if (l1.nil?) then
		begin
			f = (f * 1.25).to_i

		end while ((l1 = linear(l, f, mn, mx, k)) == nil)
	else
		while ((l2 = linear(l, f = (f / 1.25).to_i, mn, mx, k)) != nil)
			l1 = l2
		end
	end

	return l1.sort_by { |x| [-x[k]] }
end

def mid(l, k, a, b)

	l.sort_by! { |x| -x[k] }
	p(l[0...20].map { |x| x[k] })

	f = File.open('out1.txt', 'w')
	l.each { |x| f.puts(x[k]) }
	f.puts

	mx = l[0][k]
	mn = (mx * b).to_i

	c1 = l.size
	l[0..(l.size * a).to_i] = []
	mn1 = l[-1][k]
	l.delete_if { |x| x[k] < mn }
	l.each { |x| f.puts(x[k]) }
	f.close
	$stderr.puts({'mn' => mn1, 'mn2' => l[-1][k], 'mx' => mx, 'mx2' => l[0][k], 'c1' => c1, 'c2' => l.size})

end

def out(a, ks = nil, j = nil)


	fn = 'out.txt'
	fn2 = 'gnuplot.cmd'

	if ($f.nil?) then
		f = File.open(fn, 'w')
		f.puts(a.keys.join("\t"))
		f.close

		f = File.open(fn2, 'w')
		f.puts("set colors classic; set ytics nomirror; set y2tics;")
		f.close
		$f = {}
	end

	if (ks.nil?) then
		f = File.open(fn, 'a')
		f.puts(a.values.join("\t"))
		f.close
		return
	end

	if (!$f.member?([ks, j])) then
		$f[[ks, j]] = nil

		f = File.open(fn2, 'a')
		f.puts("plot \\")
		w = 25
		ks.each_with_index \
		{
			|x, i|
			y = 1
			y = 2 if (['nl', 'cg', 'c2', 'cm2', 'w2', 'v2'].member?(x))

			lw = j.nil? ? (20 - 5 * i) : 3
			t = {true => "impulse lw #{lw}", false => 'line'}[['dh', 'dl', 'd', 'dlh', 'dc'].member?(x)]

			z = 'lw 3' if (x == 'cg')
			c2 = j.nil? ? '' : "(column('j') + 0.2 * #{i}):"

			f.puts("'#{fn}' using #{c2}(column('#{x}')) with #{t} #{z} axes x1y#{y} title '#{x}', \\")
		}
		f.puts
		f.puts("pause -1")
		f.close

	end


end

p = [[3, 500], [5, 2000]]

l = sample(*p[1]).map { |x| count2(x) }

l = l.select { |x| x['d'] < 0.05 }

k = 'cg'
k = ARGV[0] if (!ARGV[0].nil?)

mid(l, k, 0.05, 0.10)

l = resample(l, k)


f = File.open("grid.txt", 'w')
l[0...20].each { |x| f.puts(x['n']) }
f.close

l.each_with_index \
{
	|x, j|

	a = data(x)
	a['j'] = j

	a['dlh'] = a['dl'] - a['dh']

	a['a01s'] = a['a1s'] - a['a0s']
	a['sd01s'] = a['sd1s'] - a['sd0s']
	a['mx01s'] = a['mx1s'] - a['mx0s']

	out(a)
	out(a, ['dlh', 'dl', 'dh', 'd', k])
	out(a, ['dlh', 'dl', 'dh', 'd', k], true)

	out(a, [k, 'mx0s', 'mx1s', 'mx01s', 'c0s', 'c1s'])
	out(a, [k, 'a0s', 'a1s', 'sd0s', 'sd1s'])
	out(a, [k, 'a01s', 'sd01s'])
}