Sum of numbers from 1 to N which are in Lucas Sequence
Given a number N. The task is to find the sum of numbers from 1 to N, which are present in the Lucas Sequence.
The Lucas numbers are in the following integer sequence:
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123 ......
Examples:
Input : N = 10 Output : 17 Input : N = 5 Output : 10
Approach:
- Loop through all the Lucas numbers which are less than the given value N.
- Initialize a sum variable with 0.
- Keep on adding these lucas numbers to get the required sum.
Below is the implementation of the above approach:
C++
// C++ program to find sum of numbers from // 1 to N which are in Lucas Sequence #include <bits/stdc++.h> using namespace std; // Function to return the // required sum int LucasSum( int N) { // Generate lucas number and keep on // adding them int sum = 0; int a = 2, b = 1, c; sum += a; while (b <= N) { sum += b; int c = a + b; a = b; b = c; } return sum; } // Driver code int main() { int N = 20; cout << LucasSum(N); return 0; } |
Java
// java program to find sum of numbers from // 1 to N which are in Lucas Sequence class GFG { // Function to return the // required sum static int LucasSum( int N) { // Generate lucas number and keep on // adding them int sum = 0 ; int a = 2 , b = 1 , c; sum += a; while (b <= N) { sum += b; c = a + b; a = b; b = c; } return sum; } // Driver code public static void main(String[] args) { int N = 20 ; System.out.println(LucasSum(N)); } // This code is contributed by princiraj1992 } |
Python3
# Python3 program to find Sum of # numbers from 1 to N which are # in Lucas Sequence # Function to return the # required Sum def LucasSum(N): # Generate lucas number and # keep on adding them Sum = 0 a = 2 b = 1 c = 0 Sum + = a while (b < = N): Sum + = b c = a + b a = b b = c return Sum # Driver code N = 20 print (LucasSum(N)) # This code is contributed # by mohit kumar |
C#
// C# program to find sum of numbers from // 1 to N which are in Lucas Sequence using System; class GFG { // Function to return the // required sum static int LucasSum( int N) { // Generate lucas number and keep on // adding them int sum = 0; int a = 2, b = 1, c; sum += a; while (b <= N) { sum += b; c = a + b; a = b; b = c; } return sum; } // Driver code public static void Main(String[] args) { int N = 20; Console.WriteLine(LucasSum(N)); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP program to find sum of numbers from // 1 to N which are in Lucas Sequence // Function to return the required sum function LucasSum( $N ) { // Generate lucas number and // keep on adding them $sum = 0; $a = 2; $b = 1; $c ; $sum += $a ; while ( $b <= $N ) { $sum += $b ; $c = $a + $b ; $a = $b ; $b = $c ; } return $sum ; } // Driver code $N = 20; echo (LucasSum( $N )); // This code is contributed // by Code_Mech. ?> |
Javascript
<script> // Javascript program to find sum of numbers // from 1 to N which are in Lucas Sequence // Function to return the // required sum function LucasSum(N) { // Generate lucas number and keep // on adding them var sum = 0; var a = 2, b = 1, c; sum += a; while (b <= N) { sum += b; var c = a + b; a = b; b = c; } return sum; } // Driver code var N = 20; document.write(LucasSum(N)); // This code is contributed by rutvik_56 </script> |
Output:
46
Time Complexity: O(n)
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us