**FRACTRAN** is a Turing-complete esoteric programming language invented by the mathematician John Horton Conway.

A FRACTRAN program is an ordered list of positive fractions , together with an initial positive integer input *n*.

The program is run by updating the integer *n* as follows:

- for the first fraction,
*f*_{i}, in the list for which*n**f*_{i}is an integer, replace*n*with*n**f*_{i}; - repeat this rule until no fraction in the list produces an integer when multiplied by
*n*, then halt.

Conway gave a program for primes in FRACTRAN:

- 17 / 91, 78 / 85, 19 / 51, 23 / 38, 29 / 33, 77 / 29, 95 / 23, 77 / 19, 1 / 17, 11 / 13, 13 / 11, 15 / 14, 15 / 2, 55 / 1

Starting with *n* = 2, this FRACTRAN program will change *n* to , then , generating the following sequence of integers:

- 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770,

After 2, this sequence contains the following powers of 2:

- 2
^{2}= 4, 2^{3}= 8, 2^{5}= 32, 2^{7}= 128, 2^{11}= 2048, 2^{13}= 8192, 2^{17}= 131072, 2^{19}= 524288,

which are the prime powers of 2.

**Your task** is to write a program that reads a list of fractions in a *natural* format from the keyboard or from a string, to parse it into a sequence of fractions (*i.e.* two integers), and runs the FRACTRAN starting from a provided integer, writing the result at each step. It is also required that the number of step is limited (by a parameter easy to find).

#include <iostream> #include <sstream> #include <iterator> #include <vector> #include <math.h> using namespace std; class fractran { public: void run( std::string p, int s, int l ) { start = s; limit = l; istringstream iss( p ); vector<string> tmp; copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( tmp ) ); string item; vector< pair<float, float> > v; pair<float, float> a; for( vector<string>::iterator i = tmp.begin(); i != tmp.end(); i++ ) { string::size_type pos = ( *i ).find( '/', 0 ); if( pos != std::string::npos ) { a = make_pair( atof( ( ( *i ).substr( 0, pos ) ).c_str() ), atof( ( ( *i ).substr( pos + 1 ) ).c_str() ) ); v.push_back( a ); } } exec( &v ); } private: void exec( vector< pair<float, float> >* v ) { int cnt = 0; bool found; float r; while( cnt < limit ) { cout << cnt << " : " << start << "\n"; cnt++; vector< pair<float, float> >::iterator it = v->begin(); found = false; while( it != v->end() ) { r = start * ( ( *it ).first / ( *it ).second ); if( r == floor( r ) ) { found = true; break; } ++it; } if( found ) start = ( int )r; else break; } } int start, limit; }; int main( int argc, char* argv[] ) { fractran f; f.run( "17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2, 15 ); return system( "pause" ); }

- Output:

0 : 2 1 : 15 2 : 825 3 : 725 4 : 1925 5 : 2275 6 : 425 7 : 390 8 : 330 9 : 290 10 : 770 11 : 910 12 : 170 13 : 156 14 : 132

Content is available under GNU Free Documentation License 1.2.