-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path#5_kyu_Product_of_consecutive_Fib_numbers.py
122 lines (95 loc) · 4.78 KB
/
#5_kyu_Product_of_consecutive_Fib_numbers.py
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
Description:
"""
The Fibonacci numbers are the numbers in the following integer sequence (Fn):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
such as
F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
Given a number, say prod (for product), we search two Fibonacci numbers F(n) and F(n+1) verifying
F(n) * F(n+1) = prod.
Your function productFib takes an integer (prod) and returns
an array:
[F(n), F(n+1), true] or {F(n), F(n+1), 1} or (F(n), F(n+1), True)depending on the language if F(n) * F(n+1) = prod.
If you don't find two consecutive F(m) verifying F(m) * F(m+1) = prodyou will return
[F(m), F(m+1), false] or {F(n), F(n+1), 0} or (F(n), F(n+1), False)F(m) being the smallest one such as F(m) * F(m+1) > prod.
Examples
productFib(714) # should return (21, 34, true),
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return (34, 55, false),
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return [21, 34, true],
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return [34, 55, false],
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return {21, 34, 1},
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return {34, 55, 0},
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return {21, 34, 1},
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return {34, 55, 0},
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return {21, 34, true},
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return {34, 55, false},
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib(714) # should return {21, 34, true},
# since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib(800) # should return {34, 55, false},
# since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
productFib 714 -- should return (21, 34, True)
-- since F(8) = 21, F(9) = 34 and 714 = 21 * 34
productFib 800 -- should return (34, 55, False),
-- since F(8) = 21, F(9) = 34, F(10) = 55 and 21 * 34 < 800 < 34 * 55
Notes: Not useful here but we can tell how to choose the number n up to which to go: we can use the "golden ratio" phi which is (1 + sqrt(5))/2 knowing that F(n) is asymptotic to: phi^n / sqrt(5). That gives a possible upper bound to n.
You can see examples in "Example test".
References
http://en.wikipedia.org/wiki/Fibonacci_number
http://oeis.org/A000045
"""
My codes:
def productFib(prod):
fab = [1,1,2,3,5]
for i in range(1000):
fab.append(fab[-1]+fab[-2])
ans = []
for i in range(1000):
ans.append(fab[i]*fab[i+1])
if ans[-1] == prod:
return [fab[i],fab[i+1],True]
elif ans[-1] > prod:
return [fab[i],fab[i+1],False]
Others codes:
def productFib(prod):
a, b = 0, 1
while prod > a * b:
a, b = b, a + b
return [a, b, prod == a * b]
def productFib(prod):
a, b = 0, 1
while prod > a * b:
a, b = b, a + b
return [a, b, prod == a * b]