Select the element out of the array if its index is a Fibonacci number I've some questions for an exam and wondered if somebody could take a look at my Fibonacci sequence that is supposed to answer this question:


  "select the element out of the array if its index is a Fibonacci number"




def fibonacci_sequence(max_num)
  sequence = [1, 2]
  loop do
    fibonacci = sequence[-2] + sequence[-1]
    break if fibonacci &gt;= max_num
    sequence &lt;&lt; fibonacci
  end
  sequence
end

# array size
max_num = 100
numbers = []
1.upto(max_num) { |num| numbers &lt;&lt; num }
fibonacci = fibonacci_sequence(max_num)

# select fibonacci numbers and assign array to variable
fibonacci_numbers = numbers.select { |num| fibonacci.include?(num) }


My thoughts were that I had to work out what the Fibonacci sequence was before I could select numbers out of the array that were Fibonacci. The thing is I already answer the question by assigning these numbers to the Fibonacci variable. I've then used a select method on the original numbers array even though I already know what the output is going to be.

Have I gone about this the right way? I'm thinking no!
Some notes:


fibonacci_numbers = numbers.select { |num| fibonacci.include?(num) }. Array#include? is O(n), this will be very slow. With this approach, fibonacci should be a set.
Since you have to store a the fibonacci values, the space complexity won't be nice for big inputs.
Your algorithm only works for arrays, it would be nice if it worked with enumerables. 


I'd write:

def remove_fib_indexes(xs)
  Enumerator.new do |yielder|
    fib_a, fib_b = [0, 1]
    xs.each.with_index do |x, idx|
      if idx == fib_a
        # skip the repeated 1 in the sequence [0, 1, 1, 2, 3, 5, ...]
        fib_a, fib_b = (fib_b == 1) ? [1, 2] : [fib_b, fib_a + fib_b] 
      else
        yielder.yield(x)
      end
    end
  end
end

xs = (0..Float::INFINITY).lazy.map(&amp;:to_s)    
remove_fib_indexes(xs).take(10).to_a
#=&gt; ["4", "6", "7", "9", "10", "11", "12", "14", "15", "16"]