Skip to content

Vidyaranya/Fibonacci

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Overview:

This repository contains programs to calculate the sum of the even fibonacci numbers in the first n terms of the series. It is done in two ways: iterative version and O(1) version. Please look below on how to run the programs and the logic behind them.

Running the program:

  1. Go the directory containing the makefile and run the command 'make'.
  2. Run ./fibonacci to run the iterative version
  3. Run ./fibonacci_advanced to run the O(1) version

Calculate the sum of the even fibonacci numbers in the first n terms of the series:

Observe that every third fibonacci number is even. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ,…

So try to write Fn in terms of Fn-3 and Fn-6
Fn = Fn-1 + Fn-2
= Fn-2 + Fn-3 + Fn-3 + Fn-4
= Fn-2 + 2Fn-3 + Fn-4
= Fn-3 + Fn-4 + 2Fn-3 + Fn-4
= 3Fn-3 + 2Fn-4
= 4Fn-3 + Fn-6

Calculate the appropriate number of even numbers and use the above formula to sum them up.

Calculate the sum of the even fibonacci numbers in the first n terms of the series in O(1):

Again using the fact that every third number is even, the sum of even fibonacci numbers can be written as sum of
((phi)3i - (psi)3i)/51/2
where 'i' is the number of even fibonacci numbers for which we want to find the sum.
phi is (1+51/2)/2 and psi = phi-1
Solving the above gives (1 / sqrt(5)) * ( phi3 * ((1 - phi3k) / (1 - phi3)) - psi3 * ((1 - psi3k) / (1 - psi3)))
where k is floor(n/3)

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published