fbpx

C++: Fractran

Bjarne-stroustrup
 

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.

Our team found a curious site for our readers that are fans of online gaming, a rather exciting site that provides the latest gaming technology. Casinodots.com is the site, they compile the best reviews of MGA casino utan svensk licens sites. This site might pique your curiosity and you can win extra money!