plateau.rb

#!/usr/bin/ruby1.8
 
 
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 % 2 == 1)
                n /= 2 while (n % 2 == 0)
                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)
 
        n3 = n
        m1 = nil
        t = 0
        dm = 0
        s = nil
        while (n != 1)
 
                n = (n * 3 + 1) / 2
                n /= 2 while (n % 2 == 0)
 
                n3 = n3 * 3
                ns = n.to_s(2)
                n3s = n3.to_s(2)
                m = match(ns, n3s)
 
                if (!m1.nil? && m != m1) then
                        puts("#{m} != #{m1}")
                        puts(s)
                        raise
                end
 
                nb = (n * 3 + 1) / 2
                nb /=2 while (nb % 2 == 0)
                nbs = nb.to_s(2)
 
                n3b = n3 * 3
                n3bs = n3b.to_s(2)
 
                d = d1 = 20
                d1 = m if (m < d1)
                break if (m > nbs.length || m > n3bs.length)
 
 
                nbs1 = nbs[m - d1...m]
                nbs2 = nbs[m...m + d]
 
                n3bs1 = n3bs[m - d1...m]
                n3bs2 = n3bs[m...m + d]
 
 
                l = nbs1 + nbs2
                r = n3bs1 + n3bs2
                m2 = match(l, r)
                d2 = m2 - d1
 
                s = "m = #{m}\td2 = #{d2}\tt = #{t}\n"
                s += [ns[0...m], ns[m..-1]].inspect + "\n"
                s += [n3s[0...m], n3s[m..-1]].inspect + "\n"
 
                s += nbs1 + ' ^ ' + nbs2 + "\n"
                s += n3bs1 + ' ^ ' + n3bs2 + "\n"
 
                m1 = m + d2
                dm = [[dm.abs, dm], [d2.abs, d2]].max[1]
 
                t += 1
 
#               raise if (d2 == nbs2.length || d2 == n3bs2.length)
 
 
        end
 
        return t, dm
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, 20].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
 
                return if (t >= 1000)
                z = l.map { |x| [x['c'], x['n']] }.max
                return z if (z[0] >= m)
        }
 
end
 
c = c2 = dm = 0
a = {}
loop \
{
        begin
                c1, n = long(100)
                c2 += 1
        end while (n.nil? || a.member?(n))
        a[n] = nil
        t, d = f2(n)
# break
        c += 1
        dm = [[dm.abs, dm], [d.abs, d]].max[1]
        p([c2, c, c1, t, d, dm, a.size.to_f / c2])
}