Hofstadter Q sequence

Using a memoized function:

func Q(n) is cached {
    n <= 2 ? 1
           : Q(n - Q(n-1))+Q(n-Q(n-2))
}
 
say "First 10 terms: #{ {|n| Q(n) }.map(1..10) }"
say "Term 1000: #{Q(1000)}"
say "Terms less than preceding in first 100k: #{2..100000->count{|i|Q(i)<Q(i-1)}}"

Using an array:

var Q = [0, 1, 1]
100_000.times {
    Q << (Q[-Q[-1]] + Q[-Q[-2]])
}

say "First 10 terms: #{Q.slice(1).first(10)}"
say "Term 1000: #{Q[1000]}"
say "Terms less than preceding in first 100k: #{2..100000->count{|i|Q[i]<Q[i-1]}}"

Output:

First 10 terms: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Term 1000: 502
Terms less than preceding in first 100k: 49798

Last updated