Sum of n fibonacci numbers
The Fibonacci sequence is a famous sequence of numbers in mathematics, where each number is the sum of the two preceding ones, starting from 0 and 1. The sum of the first n Fibonacci numbers is a common problem that has applications in various fields, including mathematics, computer science, and nature. This article aims to explain how to calculate the sum of the first n Fibonacci numbers using a C program.
Problem Statement
Given a positive integer n, the task is to calculate the sum of the first n Fibonacci numbers. The Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the previous two.
Example
For instance, if n is 7, then the first 7 Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8. Their sum is 20. If n is 10, the first 10 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, and 34. Their sum is 88.
Idea to Solve
The solution involves generating the Fibonacci sequence up to the nth number and simultaneously calculating the sum of the generated numbers. This can be done using an auxiliary array to store the Fibonacci sequence.
Pseudocode
function sum_fibonacci_number(n):
if n <= 0:
return
else:
Create an auxiliary array
Initialize sum = 0
Set first two numbers of the sequence
Iterate from 0 to n-1:
Calculate current Fibonacci number
Add current Fibonacci number to sum
Print "Sum of", n, "fibonacci numbers is", sum
function main():
sum_fibonacci_number(7)
sum_fibonacci_number(10)
Algorithm Explanation
- The
sum_fibonacci_number
function takes a single parametern
. - It first checks if
n
is less than or equal to 0. If it is, the function returns without performing any calculations. - It creates an auxiliary array to store the Fibonacci sequence and initializes the sum as 0.
- It sets the first two numbers of the Fibonacci sequence (0 and 1).
- It iterates from 0 to n-1, calculating the current Fibonacci number by adding the last two numbers in the auxiliary array.
- It adds the current Fibonacci number to the sum.
- Finally, it prints the calculated sum along with the provided value of
n
. - The
main
function tests thesum_fibonacci_number
function with different values ofn
.
Code Solution
// C Program
// Sum of n fibonacci numbers
#include <stdio.h>
//Calculating the sum of n fibonacci numbers
void sum_fibonacci_number(int n)
{
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
int auxiliary[n];
long long int sum = 0;
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
//Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
//Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// Add fibonacci number
sum += auxiliary[i];
}
printf("\n Sum of %d fibonacci number is %lld", n, sum);
}
}
int main()
{
//Test case
sum_fibonacci_number(7);
sum_fibonacci_number(10);
return 0;
}
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
// Java Program
// Sum of n fibonacci numbers
class MyMaths
{
//Calculating the sum of n fibonacci numbers
public void sum_fibonacci_number(int n)
{
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
int[] auxiliary = new int[n];
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
//Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
//resultant variable
long sum = 0;
//Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// Add fibonacci number
sum += auxiliary[i];
}
System.out.print("\n Sum of " + n + " fibonacci number is " + sum);
}
}
public static void main(String[] args)
{
MyMaths obj = new MyMaths();
//Test case
obj.sum_fibonacci_number(7);
obj.sum_fibonacci_number(10);
}
}
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
//Include header file
#include <iostream>
using namespace std;
// C++ Program
// Sum of n fibonacci numbers
class MyMaths
{
public:
//Calculating the sum of n fibonacci numbers
void sum_fibonacci_number(int n)
{
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
int auxiliary[n];
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
//Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
//resultant variable
long sum = 0;
//Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// Add fibonacci number
sum += auxiliary[i];
}
cout << "\n Sum of " << n << " fibonacci number is " << sum;
}
}
};
int main()
{
MyMaths obj = MyMaths();
//Test case
obj.sum_fibonacci_number(7);
obj.sum_fibonacci_number(10);
return 0;
}
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
//Include namespace system
using System;
// C# Program
// Sum of n fibonacci numbers
class MyMaths
{
//Calculating the sum of n fibonacci numbers
public void sum_fibonacci_number(int n)
{
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
int[] auxiliary = new int[n];
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
//Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
//resultant variable
long sum = 0;
//Calculate the sum of n fibonacci numbers
for (int i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// Add fibonacci number
sum += auxiliary[i];
}
Console.Write("\n Sum of " + n + " fibonacci number is " + sum);
}
}
public static void Main(String[] args)
{
MyMaths obj = new MyMaths();
//Test case
obj.sum_fibonacci_number(7);
obj.sum_fibonacci_number(10);
}
}
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
<?php
// Php Program
// Sum of n fibonacci numbers
class MyMaths
{
//Calculating the sum of n fibonacci numbers
public function sum_fibonacci_number($n)
{
if ($n <= 0)
{
return;
}
else
{
//create auxiliary space
$auxiliary = array_fill(0, $n, 0);
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
//Set initial sequence
$auxiliary[0] = 0;
$auxiliary[1] = 1;
//resultant variable
$sum = 0;
//Calculate the sum of n fibonacci numbers
for ($i = 0; $i < $n; ++$i)
{
if ($i > 1)
{
$auxiliary[$i] = $auxiliary[$i - 2] + $auxiliary[$i - 1];
}
// Add fibonacci number
$sum += $auxiliary[$i];
}
echo "\n Sum of ". $n ." fibonacci number is ". $sum;
}
}
}
function main()
{
$obj = new MyMaths();
//Test case
$obj->sum_fibonacci_number(7);
$obj->sum_fibonacci_number(10);
}
main();
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
// Node Js Program
// Sum of n fibonacci numbers
class MyMaths
{
//Calculating the sum of n fibonacci numbers
sum_fibonacci_number(n)
{
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
var auxiliary = Array(n).fill(0);
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
//Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
//resultant variable
var sum = 0;
//Calculate the sum of n fibonacci numbers
for (var i = 0; i < n; ++i)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// Add fibonacci number
sum += auxiliary[i];
}
process.stdout.write("\n Sum of " + n + " fibonacci number is " + sum);
}
}
}
function main()
{
var obj = new MyMaths();
//Test case
obj.sum_fibonacci_number(7);
obj.sum_fibonacci_number(10);
}
main();
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
# Python 3 Program
# Sum of n fibonacci numbers
class MyMaths :
# Calculating the sum of n fibonacci numbers
def sum_fibonacci_number(self, n) :
if (n <= 0) :
return
else :
# create auxiliary space
auxiliary = [0] * n
# Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
# Set initial sequence
auxiliary[0] = 0
auxiliary[1] = 1
# loop controlling variable
i = 0
# resultant variable
sum = 0
# Calculate the sum of n fibonacci numbers
while (i < n) :
if (i > 1) :
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
# Add fibonacci number
sum += auxiliary[i]
i += 1
print("\n Sum of ", n ," fibonacci number is ", sum, end = "")
def main() :
obj = MyMaths()
# Test case
obj.sum_fibonacci_number(7)
obj.sum_fibonacci_number(10)
if __name__ == "__main__": main()
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
# Ruby Program
# Sum of n fibonacci numbers
class MyMaths
# Calculating the sum of n fibonacci numbers
def sum_fibonacci_number(n)
if (n <= 0)
return
else
# create auxiliary space
auxiliary = Array.new(n) {0}
# Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
# Set initial sequence
auxiliary[0] = 0
auxiliary[1] = 1
# loop controlling variable
i = 0
# resultant variable
sum = 0
# Calculate the sum of n fibonacci numbers
while (i < n)
if (i > 1)
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1]
end
# Add fibonacci number
sum += auxiliary[i]
i += 1
end
print("\n Sum of ", n ," fibonacci number is ", sum)
end
end
end
def main()
obj = MyMaths.new()
# Test case
obj.sum_fibonacci_number(7)
obj.sum_fibonacci_number(10)
end
main()
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
// Scala Program
// Sum of n fibonacci numbers
class MyMaths
{
//Calculating the sum of n fibonacci numbers
def sum_fibonacci_number(n: Int): Unit = {
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
var auxiliary: Array[Int] = Array.fill[Int](n)(0);
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
//Set initial sequence
auxiliary(0) = 0;
auxiliary(1) = 1;
//loop controlling variable
var i: Int = 0;
//resultant variable
var sum: Long = 0;
//Calculate the sum of n fibonacci numbers
while (i < n)
{
if (i > 1)
{
auxiliary(i) = auxiliary(i - 2) + auxiliary(i - 1);
}
// Add fibonacci number
sum += auxiliary(i);
i += 1;
}
print("\n Sum of " + n + " fibonacci number is " + sum);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMaths = new MyMaths();
//Test case
obj.sum_fibonacci_number(7);
obj.sum_fibonacci_number(10);
}
}
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
// Swift Program
// Sum of n fibonacci numbers
class MyMaths
{
//Calculating the sum of n fibonacci numbers
func sum_fibonacci_number(_ n: Int)
{
if (n <= 0)
{
return;
}
else
{
//create auxiliary space
var auxiliary: [Int] = Array(repeating: 0, count: n);
//Sequence = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
//Set initial sequence
auxiliary[0] = 0;
auxiliary[1] = 1;
//loop controlling variable
var i: Int = 0;
//resultant variable
var sum: Int = 0;
//Calculate the sum of n fibonacci numbers
while (i < n)
{
if (i > 1)
{
auxiliary[i] = auxiliary[i - 2] + auxiliary[i - 1];
}
// Add fibonacci number
sum += auxiliary[i];
i += 1;
}
print("\n Sum of ", n ," fibonacci number is ", sum, terminator: "");
}
}
}
func main()
{
let obj: MyMaths = MyMaths();
//Test case
obj.sum_fibonacci_number(7);
obj.sum_fibonacci_number(10);
}
main();
Output
Sum of 7 fibonacci number is 20
Sum of 10 fibonacci number is 88
Time Complexity
The time complexity of this code is linear, O(n), where n is the input value. This is because the code iterates through the auxiliary array once to generate the Fibonacci sequence and calculate the sum. The execution time grows linearly with the input value.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment