fibonacci_k-th_order.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 23 January 2019
# https://github.com/trizen

# Algorithm for computing the n-th k-th order Fibonacci number, running in O(n) steps.

# OEIS sequences:
#   https://oeis.org/A000045    (2-nd order: Fibonacci numbers)
#   https://oeis.org/A000073    (3-rd order: Tribonacci numbers)
#   https://oeis.org/A000078    (4-th order: Tetranacci numbers)
#   https://oeis.org/A001591    (5-th order: Pentanacci numbers)

# See also:
#   https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Fibonacci_numbers_of_higher_order

func fibonacci_kth_order (n, k = 2) {

    # Algorithm due to M. F. Hasler
    # See: https://oeis.org/A302990

    return 0 if (n < k-1)

    var f = (1..(k+1) -> map {|j|
        j < k ? 2**j : 1
    })

    k += 1

    for i in (2*(k-1) .. n) {
        f[i%k] = (2*f[(i-1)%k] - f[i%k])
    }

    return f[n%k]
}

for k in (2..9) {
    say ("Fibonacci of k=#{k} order: ", (15 + k).of { fibonacci_kth_order(_, k) })
}

__END__
Fibonacci of k=2 order: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
Fibonacci of k=3 order: [0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768]
Fibonacci of k=4 order: [0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671]
Fibonacci of k=5 order: [0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624]
Fibonacci of k=6 order: [0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109]
Fibonacci of k=7 order: [0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808]
Fibonacci of k=8 order: [0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080, 16128]
Fibonacci of k=9 order: [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272]