generalized_lucas_closed-form.sf

#!/usr/bin/ruby

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

# A closed-form for generalized Lucas numbers:
#   a(0) = 2
#   a(1) = 1
#   a(n) = x * a(n-1) + y * a(n-2)

# Formula:
#   a(n) = (2^(-n) * ((x - 1) * (x - sqrt(x^2 + 4*y))^n + sqrt(x^2 + 4*y) * (x - sqrt(x^2 + 4*y))^n - (x - 1) * (sqrt(x^2 + 4*y) + x)^n + sqrt(x^2 + 4*y) * (sqrt(x^2 + 4*y) + x)^n))/sqrt(x^2 + 4*y)

func f(x, y, n) {
    var a = sqrt(x**2 + 4*y)
    (2**(-n) * ((x - 1) * (x - a)**n + a*(x - a)**n - (x - 1)*(a + x)**n + a*(a + x)**n))/a
}

for x,y in (1..5 ~X 1..5) {
    say ("f(#{x},#{y}) = ", 10.of { |n| f(x, y, n).round })
}

__END__
f(1,1) = [2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
f(1,2) = [2, 1, 5, 7, 17, 31, 65, 127, 257, 511]
f(1,3) = [2, 1, 7, 10, 31, 61, 154, 337, 799, 1810]
f(1,4) = [2, 1, 9, 13, 49, 101, 297, 701, 1889, 4693]
f(1,5) = [2, 1, 11, 16, 71, 151, 506, 1261, 3791, 10096]
f(2,1) = [2, 1, 4, 9, 22, 53, 128, 309, 746, 1801]
f(2,2) = [2, 1, 6, 14, 40, 108, 296, 808, 2208, 6032]
f(2,3) = [2, 1, 8, 19, 62, 181, 548, 1639, 4922, 14761]
f(2,4) = [2, 1, 10, 24, 88, 272, 896, 2880, 9344, 30208]
f(2,5) = [2, 1, 12, 29, 118, 381, 1352, 4609, 15978, 55001]
f(3,1) = [2, 1, 5, 16, 53, 175, 578, 1909, 6305, 20824]
f(3,2) = [2, 1, 7, 23, 83, 295, 1051, 3743, 13331, 47479]
f(3,3) = [2, 1, 9, 30, 117, 441, 1674, 6345, 24057, 91206]
f(3,4) = [2, 1, 11, 37, 155, 613, 2459, 9829, 39323, 157285]
f(3,5) = [2, 1, 13, 44, 197, 811, 3418, 14309, 60017, 251596]
f(4,1) = [2, 1, 6, 25, 106, 449, 1902, 8057, 34130, 144577]
f(4,2) = [2, 1, 8, 34, 152, 676, 3008, 13384, 59552, 264976]
f(4,3) = [2, 1, 10, 43, 202, 937, 4354, 20227, 93970, 436561]
f(4,4) = [2, 1, 12, 52, 256, 1232, 5952, 28736, 138752, 669952]
f(4,5) = [2, 1, 14, 61, 314, 1561, 7814, 39061, 195314, 976561]
f(5,1) = [2, 1, 7, 36, 187, 971, 5042, 26181, 135947, 705916]
f(5,2) = [2, 1, 9, 47, 253, 1359, 7301, 39223, 210717, 1132031]
f(5,3) = [2, 1, 11, 58, 323, 1789, 9914, 54937, 304427, 1686946]
f(5,4) = [2, 1, 13, 69, 397, 2261, 12893, 73509, 419117, 2389621]
f(5,5) = [2, 1, 15, 80, 475, 2775, 16250, 95125, 556875, 3260000]