Skip to content

Instantly share code, notes, and snippets.

@vznvzn
Created June 12, 2015 21:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vznvzn/aa76c416484461f01e11 to your computer and use it in GitHub Desktop.
Save vznvzn/aa76c416484461f01e11 to your computer and use it in GitHub Desktop.
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.odd?)
n /= 2 while (n.even?)
c += 1
end
return {'c' => c, 'd' => (0.5 - dense(n1)).abs}
end
def long(m)
l = [{'n' => 1, 'p' => 0}.merge(f(1))]
loop \
{
l = l.sort_by { |x| [x['c'], -x['d']] }.reverse
break if (l[0]['c'] >= m)
x = l.delete_at(rand([l.size, 2].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
}
l.sort_by! { |x| -x['c'] }
return l[0]['n'], l[0]['c']
end
def two(p)
n, c = long(p)
n0 = n
ns = n.to_s(2)
n2 = ('1' + ns[2..-1]).to_i(2)
n1 = n2
mx = mx1 = mx2 = 0
m = nil
while (n2 != 1 && n2 >= n1)
n = n * 3 + 1 if (n.odd?)
n /= 2 while (n.even?)
n2 = n2 * 3 + 1 if (n2.odd?)
n2 /= 2 while (n2.even?)
x = Math.log(n)
x2 = Math.log(n2)
m = (x - x2).abs
mx = [m, mx].max
mx1 = [mx1, x].max
mx2 = [mx2, x2].max
end
return mx, mx1 - Math.log(n0), mx2 - Math.log(n1)
end
(1..1000).each \
{
|p|
puts([p, two(p)].join("\t"))
$stdout.flush
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment