Final tribute to John Conway: FRACTRAN self-interpreter

Question

It's time to conclude the series of John Conway challenges of mine.

Background

A FRACTRAN program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

You can find some tips and tricks for writing FRACTRAN programs in the previous challenge Collatz in FRACTRAN.

Challenge

Write a FRACTRAN program that

• takes a FRACTRAN program P and its input number N encoded as an integer, and
• halts if and only if the program P halts with the input N.

Use the following procedure for encoding P to get a single positive integer f(P):

• Write down the numerator and denominator of each fraction in P in base b, using the value b as a separator.
• Read the whole thing as a single number in base b+1.

You can choose the value of b, whether to put a separator at either end or not, and which number (numerator/denominator, first fraction/last fraction) comes first in the representation. One possible encoding is:

[455/33, 11/13, 1/11, 3/7, 11/2, 1/3]
int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

The input value must be in the form of \$p^{f(P)} q^N n\$, where \$p, q\$ are two distinct primes and \$n\$ is a number coprime to \$pq\$. You can choose the values of \$p,q,n\$. (This format is consistent with the 84-fraction answer on SO and the 48-fraction one linked below.)

The shortest program in terms of the number of fractions wins.

The best record available is 48 30 24 fractions by benrg!

Answer 1

30 fractions

37^1/41^1
43^1/47^1
41^10*31^1*13^1/37^10*29^1
1/37^10
47^9*5^1/43^9*7^1
47^9/43^9*17^1
47^9/43^9*13^1
47^9/43^9*23^1
41^1*47^8/37^1*43^8*29^1
41^6*47^3/37^1*43^8*53^2
41^2*47^7*23^1*7^1/37^2*43^7*13^1*5^1
47^9*53^2/37^2*43^7*13^1
41^3*47^6*13^1/37^3*43^6*23^1
41^2*47^7*23^1*7^1*29^1/37^3*43^6*13^1*5^1
41^3*47^6/37^3*43^6*13^1
41^4*47^5*11^1/37^4*43^5*17^1
41^5*47^4*5^1/37^5*43^4*13^1
41^5*47^4/37^5*43^4*7^1
41^5*47^4/37^5*43^4*29^1
41^5*47^4*3^1/37^5*43^4*2^1
41^6*47^3*17^1/37^6*43^3*13^1
41^7*47^2*23^1/37^7*43^2*3^1
41^8*47^1*3^1*2^3/37^8*43^1*23^4
41^1*47^8*2^3*53^1/37^8*43^1*23^3
41^8*47^1*11^1*2^1/37^8*43^1*23^1
41^9*31^3/37^9*29^1
41^7*47^2*23^1*29^2/37^9*3^1
29^1/31^1
37^10*13^1/11^1
37^1/43^1

p = 2, q = 5, n = 37^5 * 43^4 * 53^1

b = 3, denominators first, last fraction first, separator at start and not at end

How does this work?

To make it easier to understand, assign meaningful names to the primes used:

ifracs=2 ifracsw=3 inum=5 inum_r=7 multiplicand=11 products=13 denominator=13 numerator=17 temp=23 multiplier=29 multiplier_r=31 stateA=37 stateA_r=41 stateB=43 stateB_r=47 p_indicator=53

Convert denominators to negative exponents, and then we can omit the ^ and * symbols (always including exponents even if 1). This produces a notation similar to Subtractpocalypse (which, as the linked page notes, becomes equivalent to FRACTRAN with a single change). Together with this, we use the name of a prime to refer to the exponent of that prime in the current number.

The state mechanism

stateA and stateB together form a state. 10 standard states (0,9), (1,8), (2,7), ..., (9,0) are chosen such that none has both components greater than or equal to another's; this way, an instruction can single out one state that it will execute only in, by subtracting the appropriate values from stateA and stateB.

To restore the state (same or different), we can't simply add back to stateA and stateB, as that would give the numerator and denominator a common factor. Instead, we add values corresponding to the new state to stateA_r and stateB_r, and the first two instructions transfer those values back to stateA and stateB:

# At the start
stateA_r -1  stateA +1
stateB_r -1  stateB +1

We use an abbreviated notation for these common parts:

State[M -> N] = stateA -M  stateB -(9-M)  stateA_r +N  stateB_r +(9-N)
State[N] = State[N -> N]

Also, the last instruction is used to automatically advance from one state to the next when nothing else executes:

# At the end
stateA +1  stateB -1

Parsing f(P)

# Start here-ish
State[5] ifracs -1  ifracsw +1
State[6] products -1  numerator +1
State[7] ifracsw -1  temp +1
State[8] temp -4  ifracsw +1  ifracs +3
State[8 -> 1] temp -3  ifracs +3  p_indicator +1

We start in state 5. There are some other instructions in state 5, but they do nothing at the start.

First, the value of f(P) is transferred from ifracs to ifracsw. The instruction in state 6 does nothing at the start.

The value is transferred from ifracsw to temp next. Then, in state 8, divide by 4 by repeatedly subtracting 4 from temp and adding 1 to ifracsw; simultaneously, 'refill' ifracs by adding the difference, which is 3, to it. After this finishes, the remainder will be left in temp.

The next instruction tests for the separator (3), changing to state 1 and also incrementing p_indicator and 'refilling' ifracs.

Suppose we haven't reached a separator. To reconstruct the base-3 number, we need to multiply the digits by 1, 3, 9, etc. This uses...

The multiplication subroutine

Multiplication happens automatically whenever the end of a state is reached, before moving on to the next state, with multiplicand nonzero. It adds to products the product of multiplicand and (multiplier+1), for a few reasons. It is implemented by these instructions:

# Multiplication (near the start)
stateA -10  stateA_r +10  multiplier -1  multiplier_r +1  products +1
stateA -10

# Multiplication (near the end)
multiplier_r -1  multiplier +1
multiplicand -1  stateA +10  products +1

The fourth of these instructions executes first. It decrements multiplicand, increments products (for the 1 added to multiplier), and adds 10 to stateA, enabling the upper two instructions. Then the first instruction runs repeatedly, transferring multiplier to multiplier_r while adding to products. The second instruction subtracts the added 10 from stateA, exiting this section, then the third instruction transfers multiplier_r back to multiplier, and this repeats until multiplicand is zero.

Back to parsing f(P)

State[8] temp -1  multiplicand +1  ifracs +1
# Multiplication occurs
State[9] multiplier -1  multiplier_r +3
State[9 -> 7] ifracsw -1  temp +1  multiplier +2

To activate multiplication, the last instruction of state 8 transfers temp to multiplicand, while 'refilling' ifracs. Multiplication occurs before the transition to state 9, adding the appropriate value for this digit to products.

Finally, we need to triple the effective multiplier, which means tripling multiplier and adding 2 to it. The instructions in state 9 accomplish that; the second one duplicates the instruction in state 7 as a way of testing whether we have reached the end of f(P), ending the program (since this is the last state) if so. (Note that, because we specified that f(P) begins with a separator, the end always happens after only one digit 0 is read, with multiplier=0, avoiding an infinite loop.)

Changing state immediately after filling multiplier_r from multiplier avoids a similar infinite loop. Going to state 7, the process repeats to read the next digit of f(P).

Handling the fraction

State[0] inum_r -1  inum +1
State[0] numerator -1
State[0] denominator -1
State[0] temp -1

State[1] multiplier -1
State[1 -> 6] p_indicator -2
State[2] denominator -1  temp +1  inum -1  inum_r +1
State[2 -> 0] denominator -1  p_indicator +2
State[3] temp -1  denominator +1
State[3 -> 2] denominator -1  temp +1  inum -1  inum_r +1  multiplier +1

p_indicator is initialised to 1, and incremented upon changing from state 8 to state 1. Thus, after reading the first (in this process; the last in the base-4 expansion) of each pair of numbers, which we have specified to be the numerator, multiplier is reset to 0, and since p_indicator is now 2, it becomes 0 with a change to state 6, where the value is transferred from products to numerator.

After reading the denominator, state 1 ends with p_indicator=1.

(Note that denominator is an alias for products -- they refer to the same prime.)

In state 2, the first instruction transfers denominator to temp and inum to inum_r simultaneously. This ends when denominator or inum reaches zero.

The second instruction checks for denominator being nonzero, which indicates that the number (original value of inum) was not divisible by the (original) denominator; it changes to state 0 while increasing p_indicator to 3. Then, the instructions in state 0 transfer inum_r back to inum, clear several values, and then continue to state 1 to clear multiplier and proceed to state 6 to resume reading f(P), with p_indicator reduced back to 1.

In state 3, temp is transferred back to denominator, and the second instruction returns to state 2 while repeating its first instruction (as before, this checks for completion) and incrementing multiplier.

If the loop exits here, then the number (original value of inum) was divisible by the (original) denominator, and multiplier contains the quotient minus 1 (for each iteration except the last).

State[3] denominator -1
State[4] numerator -1  multiplicand +1
# Multiplication occurs
State[5] products -1  inum +1
State[5] inum_r -1
State[5] multiplier -1

The final instruction of state 3 clears denominator (which is product). Then, in state 4, we transfer numerator to multiplicand, and with the transition to state 5, that value is multiplied by the quotient (recall that the multiplication subroutine uses multiplier+1). In state 5, we transfer products to inum, clear some values, and continue to repeat from the start.

The whole program with the updated notation

# Initialise: ifracs, inum; p_indicator=1, stateA=5, stateB=4
stateA_r -1  stateA +1
stateB_r -1  stateB +1

# Multiplication
stateA -10  stateA_r +10  multiplier -1  multiplier_r +1  products +1
stateA -10


State[0] inum_r -1  inum +1
State[0] numerator -1
State[0] denominator -1
State[0] temp -1

State[1] multiplier -1
State[1 -> 6] p_indicator -2
State[2] denominator -1  temp +1  inum -1  inum_r +1
State[2 -> 0] denominator -1  p_indicator +2
State[3] temp -1  denominator +1
State[3 -> 2] denominator -1  temp +1  inum -1  inum_r +1  multiplier +1

State[3] denominator -1
State[4] numerator -1  multiplicand +1
# Multiplication occurs
State[5] products -1  inum +1
State[5] inum_r -1
State[5] multiplier -1

# Start here-ish
State[5] ifracs -1  ifracsw +1
State[6] products -1  numerator +1
State[7] ifracsw -1  temp +1
State[8] temp -4  ifracsw +1  ifracs +3
State[8 -> 1] temp -3  ifracs +3  p_indicator +1
State[8] temp -1  multiplicand +1  ifracs +1
# Multiplication occurs
State[9] multiplier -1  multiplier_r +3
State[9 -> 7] ifracsw -1  temp +1  multiplier +2


# Multiplication
multiplier_r -1  multiplier +1
multiplicand -1  stateA +10  products +1

stateA +1  stateB -1

Answer 2

24 fractions

$$\frac{2}{3}, \frac{5}{7}, \frac{7^{12} 41}{5^{12} 23}, \frac{7^{13}}{5^{13} 37}, \frac{3^{10} 7^3 13}{5^{13} 31}, \frac{3^2 7^{11} 19^1 41}{2^2 5^{11} 29}, \frac{3^3 7^{10} 19^1 23}{2^3 5^{10} 29^1 41}, \frac{3^1 7^{12} 19^1 37}{2^3 5^{10} 29}, \frac{3^4 7^8 29}{2^4 5^8 19}, \frac{3^4 7^8 11^b 31}{2^4 5^8 13^{b+1}}, \frac{3^{13} 11^b}{2^4 5^9 13^b 41}, \frac{3^{12} 7^1 11^b 19}{2^5 5^8 13^b}, \frac{3^2 7^{10} 11}{2^4 5^8 13}, \frac{3^8 7^4 19^b}{2^8 5^4 29}, \frac{3^8 7^4 13}{2^8 5^4 31}, \frac{3^{12}}{2^{12} 29}, \frac{3^{13} 17^1 19}{2^{13} 37}, \frac{7^{13}}{2^{12} 5^1 23}, \frac{3^{12} 7^1 31}{2^{12} 5^1 11}, \frac{3^{12} 7}{2^{12} 5^1 17}, \frac{3^{10} 7}{2^{10} 5^1 41}, \frac{3^{10} 7^3 37}{2^{10} 5^3 17}, \frac{3^3 7^4}{2^1 5^6}, \frac{3^4 7^4}{2^8}$$

Plug in a base \$b\ge2\$ of your choice. The start state is \$31^{f(P)} 17^N 5^{13} 19\$. The program encoding has a sentinel digit on the high end only (same as m90's), and the denominator on the low end (opposite of m90's). If \$b=10\$, the program \$\frac{22}{7},\frac{355}{113}\$ encodes to int("a355a113a22a7", 11) = 32383861120629.

Explanation and annotated listing

This program uses the same double/quadruple state system as m90's 30-fraction program, but I'll call them "modes" to avoid confusion with FRACTRAN states.

A lot of the improvement of this solution comes from the observation that fractions can match ranges of modes as easily as single modes. Instead of using a subroutine or a loop variable (like m90's p_indicator) for code reuse, I use different modes with adjacent numbers, which can have any mix of shared and unshared code. Also, where m90's program has a single mode fallthrough rule at the bottom, I have two: if the mode is 1-7 then it's increased by 2, otherwise it's decreased by 4. Those two rules account for the majority of the control flow.

The basic algorithm is:

• Modes 2, 4, 6, 8 read the denominator.
• Modes 1, 3, 5, 7, 9 read the numerator while calculating \$\text{divmod}(\text{state} \times \text{numerator}, \text{denominator})\$. The intermediates (numerator and product) are never stored anywhere.
• Modes 0 and 10-13 test the remainder, update the state, rewind the program, etc.

I tried to assign similar-looking (in base 10) register numbers to related purposes. The registers are:

• 2,3,5,7 are the mode variables.
• 11,13,31 hold the program. 13 and 31 are used to parse it, and 11 is a "counterweight" adjusted so that the full program is preserved as the sum. (m90 used a similar trick.)
• 23 and 41 hold the remainder and divisor (denominator). Values of (0, d-1), (1, d−2), …, (d−1, 0) represent a divisor of d and a remainder of 0, 1, … d-1.
• 17 and 37 hold the old state (saved in case the remainder is nonzero) and the new state (quotient of the division).
• 19 and 29 hold the place value when reading the denominator, and the old state times the place value when reading the numerator (so state × numerator is calculated for free).

I'll write \$[a{,}b]\rightarrow[c{,}d]\$ (where \$d-c=b-a\ge 0\$), or just \$[a{,}b]\$ if \$a=c\$, for a factor of \$\displaystyle \frac{3^c \, 7^{13-d}}{2^a \, 5^{13-b}}\$, which means "if we're in modes \$a\$ to \$b\$ inclusive then switch to modes \$c\$ to \$d\$ and also do whatever else is in this fraction."

Also, I'll give the two-digit primes slightly more descriptive names: prg11, prg13, prg31, div23, div41, st17, st37, plc19, plc29.

Stack Exchange tables and MathJax don't play well together, so no MathJax in the table.

3−1 2+1, 7−1 5+1	Mode management, same as m90's program.
[0,0] st37−1, [0,1] div23−1 div41+1, [0,0]→[10,10] prg31−1 prg13+1	Mode 0: the designated starting point and also reached when division fails. Clear the quotient (st37) and remainder (div23). Halt if the program is exhausted, otherwise go to mode 10. The second instruction is shared with mode 1 (in fact, it's the only instruction in mode 1 aside from the default mode transition).
[10,12] div41−1, [10,10] st17−1 st37+1	Mode 10: clear the divisor and copy the saved FRACTRAN state back, then go to mode 8 (via the empty mode 6). The first instruction is shared with mode 12 (mode 11 is unused).
[8,9] plc29−1 plc19+b, [8,9] prg31−1 prg13+1	Mode 8 (denominator) or 9 (numerator): multiply the place value by b (does nothing on initial entry), and move the program to prg13, then go to mode 4/5.
[4,5] plc19−1 plc29+1, [4,5] prg13−(b+1) prg31+1 prg11+b	Mode 4/5 (den./num.): move the place value back to plc29, and compute prg31, prg13 = divmod(prg13, b+1).
[4,4]→[13,13] prg13−b prg11+b div41−1, [5,5]→[12,12] prg13−b prg11+b plc19+1	Mode 4/5: exit the loop if the sentinel digit is reached. Duplicated because they need different off-by-one fixups: after reading the denominator, decrement it, and after reading the numerator, set the place value to 1 for next time.
[4,5]→[2,3] prg13−1 prg11+1	Mode 4/5: if the digit is anything else, go to mode 2/3 to add the place value an appropriate number of times, then go to mode 8/9 (via the empty 6/7)
[2,2] plc29−1 plc19+1 div41+1	Mode 2/3: if we're reading the denominator, just add the place value.
[3,3] plc29−1 plc19+1 div41−1 div23+1, [3,3]→[1,1] plc29−1 plc19+1 st37+1	Mode 2/3: if we're reading the numerator, increment the remainder, or if it's equal to divisor−1, zero it (using mode 1) and increment the quotient. Exit to mode 4/5.
[12,13] plc29−1	Mode 12/13 (found the sentinel digit): discard the place value.
[13,13] st37−1 st17+1 plc19+1	Mode 13 (finished with the denominator): copy it to the place value and go to mode 9 to read the numerator.
[12,12]→[0,0] div23−1, [12,12] prg11−1 prg31+1, [12,12] st17−1	Mode 12 (finished with the numerator): if the remainder is nonzero then go to mode 0; otherwise, restore the original program, discard the divisor (see mode 10) and old state, and go to mode 8 to read the denominator.
[1,7]→[3,9], [8,13]→[4,9]	Default mode transitions.

Can this be improved?

Probably. It's just a PITA to satisfy all the constraints:

• The modes have to be numbered to take advantage of default fallthrough, and also to keep modes with shareable instructions together, and also the halting mode has to be on the edge so it doesn't get caught in the default-fallthrough whirlpool.
• One-time adjustments to registers can only be done during mode changes, but most of the mode changes are shared across a large number of modes. For example, m90's program tracks the place value minus 1. But that means that after you multiply it by b, you have to add b−1. But the mode transition where that would need to happen in my program is handled by the default rule, so I can't do it, or at least I don't see how.
• The challenge has strict input requirements that limit potential optimizations. For example, if I could compute the quotient (new state) minus one, it would avoid an off-by-one error when the state is added to the place value which would otherwise be 1. But then there would be no point in the loop where the interpreter state had the form \$p^\text{state}q^\text{program}n\$; the closest you'd get would be \$p^{\text{state}-1}q^\text{program}n\$.

I think the ripest candidate for improvement is the unshared fractions in modes 4 and 5. The mode offsets of the jumps are different, but that's easy to fix by rearranging the modes. plc19⁺¹ could be shared if I could subtract one from the state somewhere (as mentioned above). div41⁻¹ could be eliminated by decrementing the program before parsing the denominator. The failed-division path does that anyway, but there's no place to do it in the successful-division path. That would be a nonissue if the challenge allowed the input state to be \$p^\text{state}q^{\text{program}-1}n\$. (It's funny that both input parameters seem to be improved by subtracting 1.)

Answer 3

Here are a few solutions not written by me! If one of these is yours, please feel free to post it separately and I'll remove it from this answer. These have all been in this comment for a while, but I'm converting it to an answer for greater visibility.

Collected Answers

• 48 fracs by Chris Lomont –– SE profile, I think.

• 84 fracs by Hai-Anh Trinh –– SE profile.

• 1779 fracs by Jesse Beder –– SE profile. Generating code.