-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgeneralized_fibonacci_closed-form_3.sf
87 lines (77 loc) · 3.6 KB
/
generalized_fibonacci_closed-form_3.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#!/usr/bin/ruby
# Daniel "Trizen" Șuteu
# Date: 15 March 2018
# https://github.com/trizen
# Closed-form expression for the nth generalized Fibonacci number, F(x, y, n).
# a(0) = 0
# a(1) = 1
# a(n) = x * a(n-1) + y * a(n-2)
func a(x, y, n) {
2**(-n) * ((sqrt(x**2 + 4*y) + x)**n - (x - sqrt(x**2 + 4*y))**n) / sqrt(x**2 + 4*y)
}
# b(0) = 1
# b(1) = 0
# b(n) = x * b(n-1) + y * b(n-2)
func b(x, y, n) {
2**(-n - 1) * ((x - sqrt(x**2 + 4*y))**n + (x + sqrt(x**2 + 4*y))**n + (x * ((x - sqrt(x**2 + 4*y))**n - (x + sqrt(x**2 + 4*y))**n) / sqrt(x**2 + 4*y)))
}
for x in 1..5, y in 1..5 {
for name,f in [[:a, a], [:b, b]] {
say ("#{name}(#{x},#{y}) = ", 10.of { |n| f(x, y, n).round })
}
}
say "\nRatios of a(x,y) / b(x,y):"
say (a(2, 1, 1000) / b(2, 1, 1000)) # 1 + sqrt(2)
say (a(1, 1, 1000) / b(1, 1, 1000)) # (1 + sqrt(5)) / 2
say (a(2, 4, 1000) / b(2, 4, 1000)) # (1 + sqrt(5)) / 4
__END__
a(1,1) = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
b(1,1) = [1, 0, 1, 1, 2, 3, 5, 8, 13, 21]
a(1,2) = [0, 1, 1, 3, 5, 11, 21, 43, 85, 171]
b(1,2) = [1, 0, 2, 2, 6, 10, 22, 42, 86, 170]
a(1,3) = [0, 1, 1, 4, 7, 19, 40, 97, 217, 508]
b(1,3) = [1, 0, 3, 3, 12, 21, 57, 120, 291, 651]
a(1,4) = [0, 1, 1, 5, 9, 29, 65, 181, 441, 1165]
b(1,4) = [1, 0, 4, 4, 20, 36, 116, 260, 724, 1764]
a(1,5) = [0, 1, 1, 6, 11, 41, 96, 301, 781, 2286]
b(1,5) = [1, 0, 5, 5, 30, 55, 205, 480, 1505, 3905]
a(2,1) = [0, 1, 2, 5, 12, 29, 70, 169, 408, 985]
b(2,1) = [1, 0, 1, 2, 5, 12, 29, 70, 169, 408]
a(2,2) = [0, 1, 2, 6, 16, 44, 120, 328, 896, 2448]
b(2,2) = [1, 0, 2, 4, 12, 32, 88, 240, 656, 1792]
a(2,3) = [0, 1, 2, 7, 20, 61, 182, 547, 1640, 4921]
b(2,3) = [1, 0, 3, 6, 21, 60, 183, 546, 1641, 4920]
a(2,4) = [0, 1, 2, 8, 24, 80, 256, 832, 2688, 8704]
b(2,4) = [1, 0, 4, 8, 32, 96, 320, 1024, 3328, 10752]
a(2,5) = [0, 1, 2, 9, 28, 101, 342, 1189, 4088, 14121]
b(2,5) = [1, 0, 5, 10, 45, 140, 505, 1710, 5945, 20440]
a(3,1) = [0, 1, 3, 10, 33, 109, 360, 1189, 3927, 12970]
b(3,1) = [1, 0, 1, 3, 10, 33, 109, 360, 1189, 3927]
a(3,2) = [0, 1, 3, 11, 39, 139, 495, 1763, 6279, 22363]
b(3,2) = [1, 0, 2, 6, 22, 78, 278, 990, 3526, 12558]
a(3,3) = [0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316]
b(3,3) = [1, 0, 3, 9, 36, 135, 513, 1944, 7371, 27945]
a(3,4) = [0, 1, 3, 13, 51, 205, 819, 3277, 13107, 52429]
b(3,4) = [1, 0, 4, 12, 52, 204, 820, 3276, 13108, 52428]
a(3,5) = [0, 1, 3, 14, 57, 241, 1008, 4229, 17727, 74326]
b(3,5) = [1, 0, 5, 15, 70, 285, 1205, 5040, 21145, 88635]
a(4,1) = [0, 1, 4, 17, 72, 305, 1292, 5473, 23184, 98209]
b(4,1) = [1, 0, 1, 4, 17, 72, 305, 1292, 5473, 23184]
a(4,2) = [0, 1, 4, 18, 80, 356, 1584, 7048, 31360, 139536]
b(4,2) = [1, 0, 2, 8, 36, 160, 712, 3168, 14096, 62720]
a(4,3) = [0, 1, 4, 19, 88, 409, 1900, 8827, 41008, 190513]
b(4,3) = [1, 0, 3, 12, 57, 264, 1227, 5700, 26481, 123024]
a(4,4) = [0, 1, 4, 20, 96, 464, 2240, 10816, 52224, 252160]
b(4,4) = [1, 0, 4, 16, 80, 384, 1856, 8960, 43264, 208896]
a(4,5) = [0, 1, 4, 21, 104, 521, 2604, 13021, 65104, 325521]
b(4,5) = [1, 0, 5, 20, 105, 520, 2605, 13020, 65105, 325520]
a(5,1) = [0, 1, 5, 26, 135, 701, 3640, 18901, 98145, 509626]
b(5,1) = [1, 0, 1, 5, 26, 135, 701, 3640, 18901, 98145]
a(5,2) = [0, 1, 5, 27, 145, 779, 4185, 22483, 120785, 648891]
b(5,2) = [1, 0, 2, 10, 54, 290, 1558, 8370, 44966, 241570]
a(5,3) = [0, 1, 5, 28, 155, 859, 4760, 26377, 146165, 809956]
b(5,3) = [1, 0, 3, 15, 84, 465, 2577, 14280, 79131, 438495]
a(5,4) = [0, 1, 5, 29, 165, 941, 5365, 30589, 174405, 994381]
b(5,4) = [1, 0, 4, 20, 116, 660, 3764, 21460, 122356, 697620]
a(5,5) = [0, 1, 5, 30, 175, 1025, 6000, 35125, 205625, 1203750]
b(5,5) = [1, 0, 5, 25, 150, 875, 5125, 30000, 175625, 1028125]