23 lines
441 B
Ruby
23 lines
441 B
Ruby
@cache = []
|
|
def Q(n)
|
|
if @cache[n].nil?
|
|
case n
|
|
when 1, 2 then @cache[n] = 1
|
|
else @cache[n] = Q(n - Q(n-1)) + Q(n - Q(n-2))
|
|
end
|
|
end
|
|
@cache[n]
|
|
end
|
|
|
|
puts "first 10 numbers in the sequence: #{(1..10).map {|n| Q(n)}}"
|
|
puts "1000'th term: #{Q(1000)}"
|
|
|
|
prev = Q(1)
|
|
count = 0
|
|
2.upto(100_000) do |n|
|
|
q = Q(n)
|
|
count += 1 if q < prev
|
|
prev = q
|
|
end
|
|
puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"
|