Skip to content

Instantly share code, notes, and snippets.

@yuuki
Created August 5, 2012 18:37
Show Gist options
  • Save yuuki/3266600 to your computer and use it in GitHub Desktop.
Save yuuki/3266600 to your computer and use it in GitHub Desktop.
MAXSIZE = 1000000
MEMO = Array.new(MAXSIZE)
def collatz_size(i)
size = 0
n = i
while n != 1 do
if n <= MAXSIZE && MEMO[n]
size += MEMO[n]
break
else
n = n.even? ? n/2 : 3*n + 1
size += 1
end
end
MEMO[i] = size #メモ化
end
max = (1...MAXSIZE).each.map do |i|
{ input: i, count: collatz_size(i) }
end.max {|i, j| i[:count] <=> j[:count] }
puts max[:input]
# 837799
# 3.2s CPU: Core i5 1.6GHz, MEM: 4G
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment