# Thread: Fibonacci and decimal representation bounds

1. ## Fibonacci and decimal representation bounds

This is one task for hw, but I really have no clue. Do you?

Given b and k to be positive integers and F_k < b < F_(k+1), where Fk is the k-th fibonacci number.

Let n(b) to be the number of digits that represent b, in the decimal system.

Give the best in your opinion upper and lower bounds for n(b). The bounds have k inside them.

2. Well, the sequence continues infinitely so in all reality, it'd take an arbitrary number of bits to represent an arbitrary number in the sequence (or in between values thereof). If b is some value in-between two terms in the sequence, then you can use that to narrow down how many bits you would truly require.

It'd basically be an arbitrarily sized unsigned integer.

I'm not actually sure how libraries like GMP work in the sense that they're arbitrarily precise but I'm assuming you'd just declare a structure with a bitfield, right? Like, you can declare bitfields in structs as large as you want, right?

Edit :

Okay, I did find something. This is a very simple suggested way of implementing a big number : http://www.cplusplus.com/forum/lounge/32041/

I'm actually not sure about the specifics of your assignment but if I was given that question, that's what I would write, that theoretically an arbitrary number of bits should be used but physical constraints sort of limit that so it all depends where you want b to be.

3. So here's the Wikipedia page: Fibonacci number - Wikipedia, the free encyclopedia
And here's the OEIS page: A000045 - OEIS

I would make a mapping of k versus the number of digits in F_(k), paying extra attention to where the number of digits changes. E.g. F_(7) is the first two digit number, F_(12) the first three digit number, etc. Then, see what expression you can find that maps k to number of digits. Also note, it says "best in your opinion". I don't know that they're actually looking for the best, or most accurate, but want to see what you can come up with.

Note, I think the OEIS page has one or two little blurbs that can help you, but I'm no math expert.

4. I also thought what anduril said, but I couldn't find the mapping. Will look again in the 2nd link.

It seems that the golden ratio φ (you know, the number of Phidias of Acropolis) is the key to the answer here.

5. @MutantJohn:
I think this is more a "pure math" question, and not about programming or how to represent such numbers in a computer. std10093 can confirm.

6. I do confirm.

7. Good. I think you're right about φ. Now, how to take φ and k, and get the number of digits. Start by using φ and k to estimate the k'th term of the Fibonacci sequence. From there, it should be fairly easy to get the number of digits.

Note, my attempt gave the following. I'm limited to 92 terms based on the size of an unsigned long long on my system. Not perfect, but reasonably accurate:
Code:
```Term  Fibonacci number      Digits  Est Digits
----  --------------------  ------  ------------
2                     1       1  0.417975
3                     2       1  0.626963
4                     3       1  0.835951
5                     5       1  1.044938
6                     8       1  1.253926
7                    13       2  1.462913
8                    21       2  1.671901
9                    34       2  1.880889
10                    55       2  2.089876
11                    89       2  2.298864
12                   144       3  2.507852
13                   233       3  2.716839
14                   377       3  2.925827
15                   610       3  3.134815
16                   987       3  3.343802
17                  1597       4  3.552790
18                  2584       4  3.761778
19                  4181       4  3.970765
20                  6765       4  4.179753
21                 10946       5  4.388740
22                 17711       5  4.597728
23                 28657       5  4.806716
24                 46368       5  5.015703
25                 75025       5  5.224691
26                121393       6  5.433679
27                196418       6  5.642666
28                317811       6  5.851654
29                514229       6  6.060642
30                832040       6  6.269629
31               1346269       7  6.478617
32               2178309       7  6.687604
33               3524578       7  6.896592
34               5702887       7  7.105580
35               9227465       7  7.314567
36              14930352       8  7.523555
37              24157817       8  7.732543
38              39088169       8  7.941530
39              63245986       8  8.150518
40             102334155       9  8.359506
41             165580141       9  8.568493
42             267914296       9  8.777481
43             433494437       9  8.986469
44             701408733       9  9.195456
45            1134903170      10  9.404444
46            1836311903      10  9.613431
47            2971215073      10  9.822419
48            4807526976      10  10.031407
49            7778742049      10  10.240394
50           12586269025      11  10.449382
51           20365011074      11  10.658370
52           32951280099      11  10.867357
53           53316291173      11  11.076345
54           86267571272      11  11.285333
55          139583862445      12  11.494320
56          225851433717      12  11.703308
57          365435296162      12  11.912295
58          591286729879      12  12.121283
59          956722026041      12  12.330271
60         1548008755920      13  12.539258
61         2504730781961      13  12.748246
62         4052739537881      13  12.957234
63         6557470319842      13  13.166221
64        10610209857723      14  13.375209
65        17167680177565      14  13.584197
66        27777890035288      14  13.793184
67        44945570212853      14  14.002172
68        72723460248141      14  14.211160
69       117669030460994      15  14.420147
70       190392490709135      15  14.629135
71       308061521170129      15  14.838122
72       498454011879264      15  15.047110
73       806515533049393      15  15.256098
74      1304969544928657      16  15.465085
75      2111485077978050      16  15.674073
76      3416454622906707      16  15.883061
77      5527939700884757      16  16.092048
78      8944394323791464      16  16.301036
79     14472334024676221      17  16.510024
80     23416728348467685      17  16.719011
81     37889062373143906      17  16.927999
82     61305790721611591      17  17.136987
83     99194853094755497      17  17.345974
84    160500643816367088      18  17.554962
85    259695496911122585      18  17.763949
86    420196140727489673      18  17.972937
87    679891637638612258      18  18.181925
88   1100087778366101931      19  18.390912
89   1779979416004714189      19  18.599900
90   2880067194370816120      19  18.808888
91   4660046610375530309      19  19.017875
92   7540113804746346429      19  19.226863```

8. Oh, I totally read that problem wrong, ha ha. I thought it was asking how you code something like that. I thought they wanted the upper and lower bounds on the number of bits, not digits. Oh my God.

9. Note, my attempt gave the following. I'm limited to 92 terms based on the size of an unsigned long long on my system.
O_o

Quick and Dirty: Useful classes

Certainly nothing like "GMP" or anything, but for a quick fix for sampling like this thread, a decent set of utilities.

Soma

10. It's ok MutantJohn.

The number of results by anduril is ok, so need for GMP or such here, at least for now.

@anduril, can you explain the fourth of your column?

11. Originally Posted by std10093
@anduril, can you explain the fourth of your column?
That is the estimated number of digits in F_(k) my formula produces. Basically, it is the bounding values for n(b) in your problem. I use a very rough forumula, compared to the more accurate ones linked in Epy's post. But if you haven't read those links yet, I recommend trying to figure out a rough formula on your own. I think this is the purpose of the assignment, and it's a good mental exercise anyway. "Tuning" it to be more accurate would be fun if I had the time, but probably also goes beyond my current math skills (which have degraded significantly since I finished school).

12. Originally Posted by phantomotap
Certainly nothing like "GMP"
True, I tried with it and get very inaccurate results. (or my code sucks :P )

13. Originally Posted by std10093
True, I tried with it and get very inaccurate results. (or my code sucks :P )
What exactly did you try with GMP? Maybe your estimate formula is wrong. You could post your code.

14. What exactly did you try with GMP? Maybe your estimate formula is wrong. You could post your code.
O_o

Well, I think he was referring to using the "useful classes" I linked, but yeah, he should post the code.

If nothing else, I'm sure iMalc would like to correct any bugs.

Soma

Popular pages Recent additions