Write a program which prints the first \(50\) elements of the Fibonacci sequence. The Fibonacci sequence is initially defined as:

\[ \begin{align} f(0) &= 0 \tag{1} \\ f(1) &= 1 \tag{2} \\ f(n) &= f(n - 1) + f(n - 2) \tag{3} \\ &\quad \forall \space n \in \mathbb{N} \setminus \{0,1\} \end{align} \]

However, for each element, apply standard FizzBuzz rules. The output should look like this at the start:

FizzBuzz
1
1
2
Fizz
Buzz
8
13
...

Bonus challenge

Modify the program so that instead of printing the first \(50\) elements, allow the user to enter some value \(n\). The program should return only the \(n\)-th Fibonacci number, also applying standard FizzBuzz rules. Try to do this without recursion or iteration.

Solution

The trick to this challenge comes from knowing that Fibonacci has a closed form solution. I won't be getting into the details in how this closed form solution is derived, you can read more about that here, but solving for it gives us Binet's formula:

\[ f(n) = \frac{\phi^n - \psi^n}{\sqrt{ 5 }} \]

Where \(\phi\) is the golden ratio \(\frac{1 + \sqrt{ 5 }}{2}\) and \(\psi\) is its conjugate \(\frac{1 - \sqrt{ 5 }}{2}\). An implementation of Fibonacci in C# might look like this:

long Fibonacci(int n)
{
	const double sqrt5 = 2.23606797749979; // Math.Sqrt(5)
	const double phi = (1.0 + sqrt5) / 2.0;
	const double psi = (1.0 - sqrt5) / 2.0;

	double dividend = Math.Pow(phi, n) - Math.Pow(psi, n);
	return (long)(dividend / sqrt5);
}

Fun fact: this also means that Fibonacci doesn't just accept integers, it works for any \(n\). Sometimes the result is complex! Here's a plot of \(f(n) \space \forall \space n \in \mathbb{R}\) where the red curve denotes the real component and the blue curve is the imaginary component:

If we extend this into 3D, with the \(z\) axis representing the imaginary value, we can see that Fibonacci actually turns out to be a spiral.

Back to the problem at hand! Printing Fibonacci(0) to Fibonacci(9) yields the following:

0  
1  
1  
2  
3  
5  
8  
13  
21  
34

Now applying a standard FizzBuzz implementation and printing the first \(50\) elements lands the code at:

for (int i = 0; i < 50; i++)
{
    long result = Fibonacci(i);
    bool multipleOf3 = result % 3 == 0;
    bool multipleOf5 = result % 5 == 0;
    if (multipleOf3 && multipleOf5)
    {
        Console.WriteLine("FizzBuzz");
    }
    else if (multipleOf3)
    {
        Console.WriteLine("Fizz");
    }
    else if (multipleOf5)
    {
        Console.WriteLine("Buzz");
    }
    else
    {
        Console.WriteLine(result);
    }
}

Giving the following output:

FizzBuzz  
1  
1  
2  
Fizz  
Buzz  
8  
13  
Fizz  
34  
Buzz  
89  
Fizz  
233  
377  
Buzz  
Fizz  
1597  
2584  
4181  
FizzBuzz  
10946  
17711  
28657  
Fizz  
Buzz  
121393  
196418  
Fizz  
514229  
Buzz  
1346269  
Fizz  
3524578  
5702887  
Buzz  
Fizz  
24157817  
39088169  
63245986  
FizzBuzz  
165580141  
267914296  
433494437  
Fizz  
Buzz  
1836311903  
2971215073  
Fizz  
7778742049

From here it is trivial to implement the bonus challenge, as Fibonacci(int) has already been defined.