#include #include #include /* Hofstadter's Conway sequence Formal Definition: Q(1) = Q(2) = 1 Q(n) = Q(Q(n-1)) + Q(n-Q(n-1)) */ //////// List Device //////// // // List<...> // Add // Contains // printList // ToArray for runtime use // ///////////////////////////// class End{}; template struct List{ static const int head = t; using tail = List; }; template struct List{ static const int head = t; using tail = End ; }; template struct Add{ static const int head = L::head ; using tail = Add; }; template struct Add{ static const int head = n ; using tail = End; }; template void printList( bool isSt = true ){ if ( isSt ) std::cout << "["; else std::cout << ", "; std::cout << L::head; printList(false); } template<> void printList( bool isSt ){ std::cout << "]\n"; } template constexpr bool Contains = L::head == n || Contains; template constexpr bool Contains = false; template constexpr int Nth = Nth; template constexpr int Nth = L::head; template constexpr int Nth = -1; // runtime array conversion template struct Arr{ static int constexpr data[sizeof...( terms )] = {terms...}; }; template< typename L, int...terms> struct ToArray{ typedef typename ToArray::result result ; static int at( int n ){ // * n > length => U.B. ! ! ! return result::data[n]; } static const int length = sizeof(result::data)/sizeof(int); }; template struct ToArray{ typedef Arr result ; }; // // + + + End List Device + + + // // templatized template struct HofC{ static const int prev = HofC::result; static const int result = HofC::result + HofC::result; }; template<> struct HofC<1>{ static const int result = 1; }; template<> struct HofC<2>{ static const int result = 1; }; template struct HofCSeries{ static const int head = HofC::result; typedef HofCSeries tail; }; template struct HofCSeries{ static const int head = HofC::result; typedef End tail ; }; // recursive uint64_t rHofC( uint64_t n ){ if ( n < 3 ) return 1; int x = rHofC(n-1); return rHofC( x ) + rHofC( n - x ); } // loop // series #include std::vector getHofCSerie( uint64_t n ){ std::vector serie = {1,1,1}; for ( uint64_t i = 3 ; i <= n ; ++i ) serie.push_back( serie[ serie[ i - 1 ] ] + serie[ i - serie[ i - 1 ] ] ); return serie ; } // get value uint64_t getHofC( uint64_t n ){ return getHofCSerie( n )[ n ] ; } using namespace std; int main() { cout << "Loop uses a continer to add elements from previous making it more simple and optimized\nFor example :\nF(100000) : " << getHofC( 100000 ) << endl << endl; std::vector table = getHofCSerie(20); typedef ToArray< HofCSeries<20> > myCompileTimeSeries; std::cout << " * * Hofstadter's Conway(n) result table loop Vs recursion Vs template * *\n\n" << "input" << std::setw(10) << std::right << "loop" << std::setw(6) << std::right << "rec" << std::setw(6) << std::right << "T<>" << "\n___________________________\n" ; for ( uint64_t i = 1 ; i < table.size() ; ++i ){ std::cout << "C(" << std::setw(3) << std::right << i << ") : " << std::setw(6) << std::right << table[ i ] << std::setw(6) << std::right << rHofC( i ) << std::setw(6) << std::right << myCompileTimeSeries::at(i-1) << "\n"; } return 0; }

Algorithms [John Wells] Hofstadter's Conway sequence