 # C++: Fractran 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 $P = (f_1, f_2, \ldots, f_m)$, together with an initial positive integer input n.

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

• for the first fraction, fi, in the list for which nfi is an integer, replace n with nfi ;
• 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 $15=2\times (15/2)$, then $825=15\times (55/1)$, generating the following sequence of integers:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, $\ldots$

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

22 = 4, 23 = 8, 25 = 32, 27 = 128, 211 = 2048, 213 = 8192, 217 = 131072, 219 = 524288, $\ldots$

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

SOURCE

Content is available under GNU Free Documentation License 1.2.