fbpx

C++: Fibonacci N-Step Number Sequences

Bjarne-stroustrup
 

These number series are an expansion of the ordinary Fibonacci sequence where:

  1. For n = 2 we have the Fibonacci sequence; with initial values [1,1] and F_k^2 = F_{k-1}^2 + F_{k-2}^2
  2. For n = 3 we have the tribonacci sequence; with initial values [1,1,2] and F_k^3 = F_{k-1}^3 + F_{k-2}^3 + F_{k-3}^3
  3. For n = 4 we have the tetranacci sequence; with initial values [1,1,2,4] and F_k^4 = F_{k-1}^4 + F_{k-2}^4 + F_{k-3}^4 + F_{k-4}^4
  4. For general n > 2 we have the Fibonacci n-step sequence – F_k^n; with initial values of the first n values of the (n − 1)‘th Fibonacci n-step sequence F_k^{n-1}; and k‘th value of this n‘th sequence being F_k^n = \sum_{i=1}^{(n)} {F_{k-i}^{(n)}}

For small values of n, Greek numeric prefixes are sometimes used to individually name each series.

Fibonacci n-step sequences
n Series name Values
2 fibonacci 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …
3 tribonacci 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 …
4 tetranacci 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 …
5 pentanacci 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 …
6 hexanacci 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 …
7 heptanacci 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 …
8 octonacci 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 …
9 nonanacci 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 …
10 decanacci 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 …

Allied sequences can be generated where the initial values are changed:

The Lucas series sums the two preceeding values like the fibonacci series for n = 2 but uses [2,1] as its initial values.
The task is to
  1. Write a function to generate Fibonacci n-step number sequences given its initial values and assuming the number of initial values determines how many previous values are summed to make the next number of the series.
  2. Use this to print and show here at least the first ten members of the Fibo/tribo/tetra-nacci and Lucas sequences.

#include <vector>
#include <iostream>
#include <numeric>
#include <iterator>
#include <memory>
#include <string>
#include <algorithm>
#include <iomanip>

std::vector<int> nacci ( const std::vector<int> & start , int arity ) {
	std::vector<int> result ( start ) ;
	int sumstart = 1 ;//summing starts at vector's begin + sumstart as
	//soon as the vector is longer than arity
	while ( result.size( ) < 15 ) { //we print out the first 15 numbers
		if ( result.size( ) <= arity ) 
		result.push_back( std::accumulate( result.begin( ) , 
		result.begin( ) + result.size( ) , 0 ) ) ;
		else { 
			result.push_back( std::accumulate ( result.begin( ) +
			sumstart , result.begin( ) + sumstart + arity  , 0 )) ;
			sumstart++ ;
		}
	}
	return std::move ( result ) ;
}

int main( ) {
	std::vector<std::string> naccinames {"fibo" , "tribo" , 
		"tetra" , "penta" , "hexa" , "hepta" , "octo" , "nona" , "deca" } ;
	const std::vector<int> fibo { 1 , 1 } , lucas { 2 , 1 } ;
	for ( int i = 2 ; i < 11 ; i++ ) {
		std::vector<int> numberrow = nacci ( fibo , i ) ;
		std::cout << std::left << std::setw( 10 ) << 
		naccinames[ i - 2 ].append( "nacci" ) <<
		std::setw( 2 ) << " : " ;
		std::copy ( numberrow.begin( ) , numberrow.end( ) ,
		std::ostream_iterator<int>( std::cout , " " ) ) ; 
		std::cout << "...\n" ;
		numberrow = nacci ( lucas , i ) ;
		std::cout << "Lucas-" << i ; 
		if ( i < 10 )               //for formatting purposes
		std::cout << "    : " ;
		else 
		std::cout << "   : " ;
		std::copy ( numberrow.begin( ) , numberrow.end( ) ,
		std::ostream_iterator<int>( std::cout , " " ) ) ; 
		std::cout << "...\n" ;
	}
	return 0 ;
}

Output:

fibonacci  : 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ...
Lucas-2    : 2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 ...
tribonacci : 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ...
Lucas-3    : 2 1 3 6 10 19 35 64 118 217 399 734 1350 2483 4567 ...
tetranacci : 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ...
Lucas-4    : 2 1 3 6 12 22 43 83 160 308 594 1145 2207 4254 8200 ...
pentanacci : 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ...
Lucas-5    : 2 1 3 6 12 24 46 91 179 352 692 1360 2674 5257 10335 ...
hexanacci  : 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ...
Lucas-6    : 2 1 3 6 12 24 48 94 187 371 736 1460 2896 5744 11394 ...
heptanacci : 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ...
Lucas-7    : 2 1 3 6 12 24 48 96 190 379 755 1504 2996 5968 11888 ...
octonacci  : 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ...
Lucas-8    : 2 1 3 6 12 24 48 96 192 382 763 1523 3040 6068 12112 ...
nonanacci  : 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ...
Lucas-9    : 2 1 3 6 12 24 48 96 192 384 766 1531 3059 6112 12212 ...
decanacci  : 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ...
Lucas-10   : 2 1 3 6 12 24 48 96 192 384 768 1534 3067 6131 12256 ...

Alternate Version

This version focuses on a clean, simple class that adapts to any pair of starting numbers and any order. Rather than summing over all history every time, it uses an O(1) incremental update to a running total. Thus, performance remains essentially unchanged even for very large orders.

#include <iostream>
#include <vector>

// This class forms a simple 'generator', where operator() returns the next
// element in the series.  It uses a small sliding window buffer to minimize
// storage overhead.
class nacci_t
{
	std::vector< int >  history;
	unsigned            windex;             // sliding window index
	unsigned            rindex;             // result index
	int                 running_sum;        // sum of values in sliding window

public:

	nacci_t( unsigned int order, int a0 = 1, int a1 = 1 )
	:   history( order + 1 ), windex( 0 ), rindex( order - 1 ), 
	running_sum( a0 + a1 )
	{
		// intialize sliding window
		history[order - 1] = a0;
		history[order - 0] = a1;
	}

	int operator()() 
	{
		int result   = history[ rindex ];   // get 'nacci number to return
		running_sum -= history[ windex ];   // old 'nacci falls out of window

		history[ windex ] = running_sum;    // new 'nacci enters the window
		running_sum      += running_sum;    // new 'nacci added to the sum

		if ( ++windex == history.size() ) windex = 0;
		if ( ++rindex == history.size() ) rindex = 0;

		return result;
	}
};

int main()
{
	for ( unsigned int i = 2; i <= 10; ++i )
	{
		nacci_t nacci( i ); // fibonacci sequence 

		std::cout << "nacci( " << i << " ): ";

		for ( int j = 0; j < 10; ++j )
		std::cout << " " << nacci();

		std::cout << std::endl;
	}

	for ( unsigned int i = 2; i <= 10; ++i )
	{
		nacci_t lucas( i, 2, 1 ); // Lucas sequence 

		std::cout << "lucas( " << i << " ): ";

		for ( int j = 0; j < 10; ++j )
		std::cout << " " << lucas();

		std::cout << std::endl;
	}
}

SOURCE

Content is available under GNU Free Documentation License 1.2.