Cruelty of Covid 19

Cruelty of covid 19 John H Conway        Fractran and primes

DOI: 10.13140/RG.2.2.32436.2752

The great British-American Mathematician John H Conway passed away on 11th april 2020 due to covid -19 a cruel virus which did not recognize the great brain it attacked. John Conway was born in England on 26th December 1937is known for many contributions first for his game of life a celllar automaton. Secondly He created surreal numbers a nonarchimedean ordered field which is a superset of the field of real numbers and the mathematician Donald knuth wrote a novel “surreal numbers”. He worked in coding theory knot theory , combinatorial game theory group theory and led the programme of classification of finite groups.

He created the remarkable language Fractran and his program of prime numbers is famous.

We describe this number theory language fractran give conways remarkable prime number program and we have written our own code the interpreter for Fractran language.

Basics :Ffractran is a language in which each program is simply an array P of positive fractions .Each fraction is in its lowest terms. The program is executed by multiplying by an integer seed n supplied.

 The algorithm is as follows

1 Multiply each term of the array P by n

2 When the result is an integer stop and replace n ny n.f

3 Repeat the process from step 1 placing n by n.f.

Innocent as it sounds but the genius of Conway is that, the language Fractran is such that  a program is a simple array of positive fractions. The instructions are supplied by each term in the array in an ingenious  Mathematical fashion.

Godel Numbering : The          language is based on the principal of Godel numbering. Each number can be uniquely factorized into a power of primes.

So the primes occurring in the factorization are registers and the powers are the values in the register which at every move encodes state of the computer.

Addition fractran Program : We illustrate the  simple fractran program for addition.

program [ ] = {3/2}.

 Yes the program is an array of fractions consisting of only one term 3/2

To add two numbers a and b we simply supply the seed n as 2a.3b.

 when we multiply by n to the fraction, the power of 2 gets decremented and the power of 3 gets incremented.

Now n becomes n.3/2 that is 2a-13b+1.

When the process is repeated   again register 2 is decremented and register 3 is incremented and  n is changed.

After “a” number steps we can not do the process and stop as in register 2 value is0. But in register 3 value is a+b that is 3a+b.

Prime generator using a sieve of only 10 primes Perhaps the most ingenious fractran program is prime number generator. by using a limited sieve of prime numbers upto 30 the program can generate all primes .

We take the seed n =2 and each time the new value of n is a power of 2 that power is the next prime number. here is the program.

Program [  ] ={17/91,78/85,19/51,23/38,29/33,77/29,95/23 77/19,1/17,11/13,

 13/11, 15/2,1/7, 55/1}

Please note that due to the denominator of last fraction being1 it will divide any n and thus the program is set in an infinite loop.

The values of n when they are powers of 2 , the exponents are successive primes generated.

 Subtraction Program : To subtract b from a we input 2a.3b the output is 2a-b.

The program is program [ ] = [1/6}.

Tt is clear that each time when we multiply, a power of 2 is incremented  and a power of 3 is decremented.

Since a > b what remains is t2a-b.

Some insights into working of Fractran :each prime used say 2 or 3 stands for a register. We think of 2 as register v2. 3,as register v3 and so on.

Since the FRACTRAN program is just a list of fractions, these test-decrement-increment instructions are the only allowed instructions in the FRACTRAN language. In addition the following restrictions apply:

·       Each time an instruction is executed, the variables that are tested are also decremented.

·       The same variable cannot be both decremented and incremented in a single instruction otherwise the fraction representing that instruction would not be in its lowest terms .

·       Therefore each FRACTRAN instruction consumes variables as it tests them.

It is not possible for a FRACTRAN instruction to directly test if a variable is 0 (However, an indirect test is implemented by creating a default instruction that is placed after other instructions that test a particular variable.).

Another  detailed way to look at it: Like most simple languages, Fractran has two clearly defined spaces, one for data and one for instructions.

The data is stored in a series of registers, which each can store an integer value.

The instructions are stored as a list, and are all formed by the following statement:

IF(registers X, Y, Z are all non-zero)

THEN(decrement registers X, Y, Z (possibly multiple times); increment registers P, Q, R (possibly multiple times); go to label "begin")

The program itself is always of the following form:

LABEL: begin

instruction1

instruction2

instruction3

etc.

END PROGRAM

The registers are stored with a variant on Godel-numbering, where each register is represented by raising a corresponding prime to the register's value and then they're all multiplied together into I. And the instructions are represented as fractions, where registers X, Y, and Z are primes in the denominator and registers P, Q, and R are primes in the numerator. If you want to increment/decrement more than once, just put the primes in there multiple times

A multiplication Program : multiplication is repeated addition So we have to set a loop.

To multiply 2 numbers a and b we take n as 2a3b and output is 5ab.:

:

Current State

Condition

Action

Next State

A

v7 > 0

Subtract 1 from v7

Add 1 to v3

A

v7 = 0 and

v2 > 0

Subtract 1 from v2

B

v7 = 0 and

v2 = 0 and

v3 > 0

Subtract 1 from v3

A

v7 = 0 and

v2 = 0 and

v3 = 0

Stop

B

v3 > 0

Subtract 1 from v3

Add 1 to v5

Add 1 to v7

B

v3 = 0

None

A

State B is a loop that adds v3 to v5 and also moves v3 to v7, and state A

State B is a loop that adds v3 to v5 and also moves v3 to v7, and state A is an outer control loop that repeats the loop in state B v2 times. State A also restores the value of v3 from v7 after the loop in state B has completed.

We can implement states using new variables as state indicators. The state indicators for state B will be v11 and v13. Note that we require two state control indicators for one loop; a primary flag (v11) and a secondary flag (v13). Because each indicator is consumed whenever it is tested, we need a secondary indicator to say "continue in the current state"; this secondary indicator is swapped back to the primary indicator in the next instruction, and the loop continues.

Adding FRACTRAN state indicators and instructions to the multiplication algorithm table, we have:

FRACTRAN

Instruction

Current State

State

Indicators

Condition

Action

Next State

3/7{\displaystyle {\frac {3}{7}}}

A

None

v7 > 0

Subtract 1 from v7

Add 1 to v3

A

11/2{\displaystyle {\frac {11}{2}}}

v7 = 0 and

v2 > 0

Subtract 1 from v2

B

1/3{\displaystyle {\frac {1}{3}}}

v7 = 0 and

v2 = 0 and

v3 > 0

Subtract 1 from v3

A

5.7.13/ 3.

11/13

v7 = 0 and

v2 = 0 and

v3 = 0

Stop

1/11{\displaystyle {\frac {5\cdot 7\cdot 13}{3\cdot 11}},{\frac {11}{13}}}

B

v11, v13

v3 > 0

Subtract 1 from v3

Add 1 to v5

Add 1 to v7

B

{\displaystyle {\frac {1}{11}}}

v3 = 0

None

A

When we write  the FRACTRAN instructions, we must put the state A instructions last, because state A has no state indicators - it is the default state if no state indicators are set.

So we get a fractran program for multiplication.

program [ ] = {455/33, 11/13, 1/11,3/7, 11/2,1/3}

Interesting facts

Fractran is Turing complete. Turing machine is an abstract computer that can compute output of each program on natural numbers.

So Fractran is essentially a numerical programming model of Turing machine. So every program like GCD , Hello world , fibonaccci numbers can be written in Fractran.

our own interpreter of Fractran in C

We have written our own interpreter of fractran in C. Any frctran program will be interpreted  we have illustrated addition multiplication subtraction division and primes.

The input is a fractran program given by the array program [ ], an array of integers.

Each fraction can be written as a pair of integers numerator and denominator.

Further we do not want very big numbers generated so we have factorized numerator and denominator each into 3 factors.

Thus fraction 33/ 70 will be given by 6 integers 3,11, 1, 2, 5, 7

So the program is an array of integers.

We do not need seed. The seed is is usually 1 and program only accepts 0,1 or more arguments.

Division program needs  the seed  11 and a seed is typically taken care by starting the program array with 0 Seed 11 will be taken care as starting  3 terms 0,11, 1 is the power of 11, the seed to be used. .

If the program array does not begin with 0, the seed is 1.

To end the program we add a simple term 0 in the array  at the end of the array.

Rest of the logic is fairly simple When arguments like a and b are accepted automatically we store 2a and 3b.

We have an array of prêt ermined seeds which lists all ten primes from 0 to 29.

Seed is an array of registers . The  seed value 2 means register v2.

We need an auxiliary array index [ ] to storethe  powers of primes. These arere values stored  in the corresponding registers

We need the array sindex for back up.

We need a variable flag to set up ,  as in the case of infinite loop like prime.

Output will be in the  register for prime 2 and flag will check that all other registers store 0. sflag is back up.

The outputs will be given directly by checking that only registers with nonzero values give the output at the end.

The division program generates two outputs remainder and quotient in two different registers.

The program carries comments for detail flow of  ,logic.

We simply multiply by n the initial value formed automatically to the array program [ ].

Test whether each factor of the denominator divides and in that case we multiply n by each value of numerator factor and start all over again

 else move to the  next fraction.

 Thus variable I is incremented by 56 as 3 factors in numerator and 3 in denominator.

For prime numbers we input number of arguments as 0 .

It initializes seed n on its own.

The c program is included alongwith

References

1)   Wikipedia –Fractran

2). Conway, John H. (1987). "FRACTRAN: A simple universal programming language for arithmetic". Open Problems in Communication and Computation. Springer-Verlag New York, Inc.: 4–26. .

 ISBN 978-1-4612-9162-6.

 doi:10.1007/978-1-4612-4808-8_

3) Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc. ISBN 0-387-97993-X.

2)   

Please turn on

Code of o ur c interpreter for Fractran   (separate c file is also included)

/*int program [ ] ={17/91,78/85,19/51,23/38,29/33,77/29,95/23 77/19,1/17,11/13, 13/11, 15/2,1/7, 55/1};   */

/*for primes . input number of arguments as 0…8/

?* the above array is rewritten below as an array of integers with 3 factors for each numerator and denominator */

/* int program [ ] ={17,1,1, 13,7,1,  13,3,2, 17,5,1, 19,1,1, 17,3,1,

                                          23,1,1, 19,2,1, 29,1,1, 11,3,1,  11,7,1, 29,1,1,

                                          19,5,1, 23,1,1,  11,7,1, 19,1,1,  1,1,1, 17,1,1,

                                          11,1,1, 13,1,1, 13,1,1, 11,1,1, 5,3,1,   2,1,1,

                                          1,1,1, 7,1,1, 11,5,1,   1,1,1, 0}; */

                                          /*last fraction den is 1 so infinite loop*/

/* int program [ ] = { 3,1,1,2,1,1,0};    For addition               */

/*int program [ ]={1,1,1,2,3,1}; */ /*for subtraction */

/* next one is for multioplication and again made array of integers */

/* multiply program [ ]={455/33, 11/13, 1/11,3/7, 11/2,1/3} */

/* int program [  ]= {13,7,5, 11,3, 1, 11,1,1, 13,1,1, 1,1,1, 11,1,1,

                                          3,1,1, 7,1,1,  11,1,1, 2,1,1,  1,1,1, 3,1,1, 0}; */

/*division program [ ]={91/66,11/13,1/33,85/11,57/119,17/19,11/17,1/3 }*/

 int program [ ] = {0,11,1,13,7,1, 11,3,2, 11,1,1, 13,1,1, 1,1,1, 11,3,1,

                                17,5,1, 11,1,1, 19,3,1, 17,7,1, 17,1,1, 19,1,1,

                                11,1,1, 17,1,1,  1,1,1, 3,1,1, };

#define size 10

void main ( )

{ int n = 0, a = 0,p = 0, found = 0, i, factor=0 ,j, k, key;

unsigned long s, sflag=0, flag=0;

int seed[] = {2,3,5,7,11,13,17,19,23,29,0};

unsigned long index[] = {1,0,0,0,0,0,0,0,0,0,0};

unsigned long sindex[] = {1,0,0,0,0,0,0,0,0,0,0};

clrscr();

printf("\n Number ofarguments ");

scanf ("%d", &a);

for ( j = 0; j <=size && j<a ; j++)

 {  printf ("give argument%d ",j );

     scanf ("%lu", &index[j]);

    sindex[j]=index[j];

    if (j!=0) {flag++;sflag++;}

  }

I f(program [0] == 0 )  /* if there is initial seed */

 { p=3,n=program[1],s=(unsigned long)program[2]; found=0;

for (j=0; j<=size && !found ; j++)

              {if(seed[j] == program[1])  found=1; }

 printf("\n%d,%d,%lu",j-1,seed[j-1]=n,sindex[j-1]+=s);index[j-1]+=s;

          if (j!=1){ flag++; sflag++; }

}

for ( i =p; (program[i] != 0) && !factor; i+=6)

           /* as long as not reached  the end of program array of rationals*/

  { factor = 1; /* set factor=1 so that we enterloop*/

/*see if Den of next fraction divides seed by checking 3 factors given by k value*/

                     for (k =3; factor && (key= program[i+k])!=1 && k <6; k++ )

                               { key = program[i+k]; factor=0;

/*key is next factor to be checked. Need not check if it is 1.reset factor=0*/

                                         for ( j =0; seed[j] != 0 && !factor ; j++)

                                          {if (seed[j] == key)

/*see whether key matches with factor in seed factor*/

  {                          if (index [j] ==0) factor=0; /*no factor not there*/

                               else

                               { factor=1; --sindex[j] ;/*matches factor is seed*/

                               if ( j !=0 ) --sflag;

  }/*update backup copies of flag and factor index*/

                                }

                    }  /*if all 3 factors o fden present in seed den is factor of seed*/

           if ( factor!= 0)

             /*as Den is factor backup actual index & flag */

                      { for (k=0; k<=size; k++)  index[k] = sindex[k];

                                flag = sflag;

                                for (k =0 ; k < 3 && (key =program[i+k])!=1 ; k++)

                                      {/*now multiply by numerator 3 factors*/

                                           found=0;

                                           for ( j =0; seed[j] != 0 &&!found ; j++)                                                                {

                                                        if ( seed[j] == key )

                                                           { index[j]++;found=1;

                                                              sindex[j]++;/*also backup*/

                                                               if ( j !=0) { flag++; sflag++; }

                                                     }

                                         }

                                          if (!found)

{ seed[j]=key; index[j]++,sindex[j]++;  flag++;sflag++;

}

                                          }

           if( flag==0 && a==0)/*as result is stored as power of I factor in seed*/

                      { /*flag is 0in begining & should be 0 atvend so no other factors*/

                                          printf("%lu ", index[0]);

                      }

                      i =p - 6; /* start with fesh seed init and from i =0 */

                      factor = 0;/* updated seed. Start all over again*/

            }

          for(k=0;k<=size;k++)sindex[k]=index[k];sflag=flag;

/*As all 3 factors ofden dont divide seed not afactor Restore backup copies*/

  } /*move to check for next factor in outermost loop*/

  for (j=0;j<size;j++)if (index[j])

     printf("\nanswers %d %d %lu" ,j,seed[j], index[j]);

}

{\displaystyle \left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)}