fibonacci_k-th_order_2.sf

#!/usr/bin/ruby

# A new formula for computing the n-th k-th order Fibonacci number in O(n/k) steps.

# Reference:
#   Some applications of the Lagrange inversion formula for the k-Fibonacci numbers, by Bakir FARHI

func fibonacci_kth_order(n,k=2) {
    1<<(n-k) + sum(1 .. idiv(n - k + 1, k+1), {|l|
        (-1)**l * (binomial(n - k*(l+1) + 1, l) + binomial(n - k*(l+1), l-1)) << (n - l*(k+1) - 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, 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
Fibonacci of k=3 order: [0, 0, 0, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768]
Fibonacci of k=4 order: [0, 0, 0, 0, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671]
Fibonacci of k=5 order: [0, 0, 0, 0, 0, 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, 0, 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, 0, 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, 0, 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, 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272]