(In this post, “number” means “positive integer”.)

Simply speaking, if we substitute 2’s or 10’s power system as the basis for presentation with Fibonacci series, we can get Fibonacci “based” number system.

For example, number 16 (base 10) can be converted into Fibonacci number system like this:

16 -> The biggest smaller Fibonacci number 13 take out 1 time -> Remainder is 3

3 –> The biggest smaller Fibonacci number 8 take out 0 time –> Remainder is 3

3 –> The biggest smaller Fibonacci number 5 take out 0 time –> Remainder is 3

3 –> The biggest smaller Fibonacci number 3 take out 1 time –> Remainder is 0

0 –> The biggest smaller Fibonacci number 2 take out 0 time –> Remainder is 0

0 –> The biggest smaller Fibonacci number 1 take out 0 time –> Remainder is 0

(and ignore the first Fibonacci number 1)

Output -> 16 (base 10) = 100100 (base Fibonacci).

It is easy to see that:

- Each number has unique representation
- Each representation has unique number
- Because for n>3, Fibonacci(n) < 2 * Fibonacci(n-1), the representation is using only 2 symbols, 1 and 0
- Because Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), there could be no two consecutive 1s in Fibonacci number system. 0110 (base Fibonacci) is the same as 1000 (base Fibonacci) and the only latter one is valid
- Because 11 is an invalid sequence, Fibonacci presentation of a number will be longer than base 2 presentation (normal binary)

Stay tuned for the code and more observations about basic arithmetic operations – or start sharing here 🙂

BTW, we can use any strictly increasing monotonic series as the basis for a number system which has first element as 1. (That is, it is possible to come up with factorial number system also.)

Here is the code:

*using namespace std;*

*#include <iostream>*

* #include <string>*

* #include <fstream>*

*const int size = 50; // maximum size of presentation*

* unsigned long int f[size]; // place value holder*

*int value = 100; // number of integers to convert*

*void fill (unsigned long int *f);*

* void convert (int i, int j, std::string &s);*

* int findMSP (int i);*

*int main(int argc, char** argv) {*

* ofstream outfile;*

* outfile.open(“FibonacciNumbers.csv”);*

*// Create a long enough place value array*

* fill(f);*

*// now convert integers from 1 through ‘value’ to the new place value system*

* for (int i = 1; i < value; i++) {*

* std:string presentation;*

* convert(i, findMSP(i), presentation);*

* outfile << i << “,” << presentation << endl; *

*} *

*outfile.close(); *

*return 0;*

*}*

// core logic

*void convert (int i, int j, std::string &s) { *

*int mul = i/f[j]; *

*i %= f[j]; *

*s.append(1,(char)mul+’0′); *

*if (j >= 1) convert (i, –j, s);*

* else return;*

* }*

*// just how many places are needed for the number in the new place value system*

* int findMSP (int i) {*

* int j = size – 1;*

* for (; j >=1; j–) {*

* if (f[j] <= i) break;*

* }*

* return j;*

* }*

*void fill (unsigned long int *f) {*

* // fibonacci for now*

* f[0] = 1;*

* f[1] = 2;*

* for (int i = 2; i < size; i++) {*

* f[i] = f[i-1] + f[i-2];*

* }*

* }*