35
\$\begingroup\$

John Horton Conway was a brilliant mathematician. Among his contributions were three Turing-complete esolangs: Game of Life (esolangs wiki), FRACTRAN (esolangs wiki), and Collatz function (esolangs wiki).

Because we did an extremely amazing job around GoL, it is time for the challenge with the other two.

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.

A Collatz sequence is defined as the following: given a positive integer \$n\$,

$$ \begin{align} a_0 &= n \\ a_{i+1} &= \begin{cases} a_i/2, & \text{if $a_i$ is even} \\ 3a_i+1, & \text{if $a_i$ is odd} \end{cases} \end{align} $$

It is conjectured that, for every positive integer \$n\$, the sequence eventually reaches 1.

Task

Write a FRACTRAN program that takes \$p^n\$ as input (for a prime \$p\$ of your choice) and halts if and only if the Collatz sequence starting at \$n\$ reaches 1.

You may see Avi F. S.'s COLLATZGAME as an example. Also, TIO has an implementation of FRACTRAN, so you can test your program with it. (Enter the starting number in the Arguments section; it accepts base-exponent form e.g. 2^27 as well as plain integer form.)

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

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Why didn't you think of interpreting FRACTRAN with iterations of the Collatz function? \$\endgroup\$
    – user92069
    Apr 20, 2020 at 1:55
  • 2
    \$\begingroup\$ @petStorm Because that one doesn't have a known interpreter. \$\endgroup\$
    – Bubbler
    Apr 20, 2020 at 1:59
  • \$\begingroup\$ Is the onus on the writer of the program to prove its correctness? :-) \$\endgroup\$ Apr 20, 2020 at 22:30
  • \$\begingroup\$ @MeesdeVries Yes. We don't require a rigorous proof in the mathematical sense, but an answer should at least convince the reader that it is correct. \$\endgroup\$
    – Bubbler
    Apr 20, 2020 at 23:19
  • \$\begingroup\$ Would a program 1/2 for inputs of form 3^n be a correct solution if the collatz conjecture were proven to be true? \$\endgroup\$
    – Sopel
    Apr 24, 2020 at 20:26

2 Answers 2

35
\$\begingroup\$

9 8 7 fractions

$$\frac{5}{4}, \frac{63}{22}, \frac{14}{55}, \frac{66}{35}, \frac{1}{7}, \frac{2}{3}, \frac{44}{5}$$

Takes input as \$3^n\$.

Try it online!

How it works

The first transition is

$$3^n \xrightarrow{\frac{2}{3}} 2 \cdot 3^{n - 1},$$

which we will consider the “real” representation of the number \$n\$, because some intermediate control flows will bypass the above transition.

If \$n = 1\$, the program now halts immediately.

If \$n = 2k\$ is even, we have

$$\begin{multline*} 2 \cdot 3^{2k - 1} \xrightarrow{\frac{2}{3}} 2^2 \cdot 3^{2k - 2} \xrightarrow{\frac{5}{4}} 3^{2k - 2} \cdot 5 \xrightarrow{\left(\frac{2}{3} \cdot \frac{2}{3} \cdot \frac{5}{4}\right)^{k - 1}} 5^k \xrightarrow{\frac{44}{5}} 2^2 \cdot 5^{k - 1} \cdot 11 \\ \xrightarrow{\frac{5}{4}} 5^k \cdot 11 \xrightarrow{\frac{14}{55}} 2 \cdot 5^{k - 1} \cdot 7 \xrightarrow{\left(\frac{66}{35} \cdot \frac{5}{4} \cdot \frac{14}{55}\right)^{k - 1}} 2 \cdot 3^{k - 1} \cdot 7 \xrightarrow{\frac{1}{7}} 2 \cdot 3^{k - 1}, \end{multline*}$$

which represents \$\frac{n}{2}\$.

If \$n = 2k + 1\$ is odd, we instead have

$$\begin{multline*} 2 \cdot 3^{2k} \xrightarrow{\left(\frac{2}{3} \cdot \frac{5}{4} \cdot \frac{2}{3}\right)^k} 2 \cdot 5^k \xrightarrow{\frac{44}{5}} 2^3 \cdot 5^{k - 1} \cdot 11 \xrightarrow{\frac{5}{4}} 2 \cdot 5^k \cdot 11 \\ \xrightarrow{\frac{63}{22}} 3^2 \cdot 5^k \cdot 7 \xrightarrow{\left(\frac{66}{35} \cdot \frac{63}{22}\right)^k} 3^{3k + 2} \cdot 7 \xrightarrow{\frac{1}{7}} 3^{3k + 2} \xrightarrow{\frac{2}{3}} 2 \cdot 3^{3k + 1}, \end{multline*}$$

which represents \$3k + 2 = \frac{3n + 1}{2}\$, which is two steps ahead of \$n\$.

\$\endgroup\$
4
  • \$\begingroup\$ Could you please provide an explanation? \$\endgroup\$ Apr 20, 2020 at 2:53
  • 3
    \$\begingroup\$ @mypronounismonicareinstate After I finish optimizing! \$\endgroup\$ Apr 20, 2020 at 2:54
  • \$\begingroup\$ What was the procedure (or flowchart, etc) for deriving those fractions? Was it "easier" to work backwards from a final fraction? \$\endgroup\$ Apr 21, 2020 at 13:46
  • 1
    \$\begingroup\$ @CarlWitthoft I can't speak for Anders, but here's my analysis of his program: gist.github.com/kmill/266ef6bb5690f9c26110673dcc59f710 It has some real cleverness in getting around some of FRACTRANs quirks! And also how it calculates \$2r+(1+2r)d\$ where \$d\$ is the floor of \$n/2\$ and \$r\$ is the remainder of this quotient. \$\endgroup\$ Apr 21, 2020 at 19:54
16
\$\begingroup\$

9 fractions

13/11 22/39 1/13 7/5 320/21 1024/7 3/4 5/6 22/3

Try it online! Input is a power of 2.

It's probably easier to think about FRACTRAN code in terms of the powers of the primes in each fraction. I list these below for the code, with positive exponents coming from numerators and negative values from denominators, omitting 0's to reduce clutter. Thinking of programs as lists of vectors and the current value as a vector, FRACTRAN repeatedly modifies the value by adding the first-listed row such this results in no negatives entries.

  2  3  5  7 11 13
  ----------------
             -1 +1
 +1 -1       +1 -1
                -1
       -1 +1      
 +6 -1 +1 -1      
+10       -1      
 -2 +1            
 -1 -1 +1         
 +1 -1       +1  

I suspect this solution is similar to Anders Kaseorg's earlier 9-byte solution, who has already explained how his now-more-golfed answer works in detail. So, I'll instead explain a useful conceptual idea in my code.

Switcher gadget

I'll talk about a control flow gadget that I'll call a switcher that my code heavily relies on. You can see two copies of it, one in columns 3 and 4, and another in columns 5 and 6. It looks like this:

   -1 +1
B  +1 -1
b     -1
A
a  +1

Here, A, a, B, and a are some FRACTRAN operations, taking up multiple columns. A switcher alternates between two things:

  • Repeat A as long as it's legal, then do a once.
  • Repeat B as long as it's legal, then do b once.

The first row -1 +1 doesn't do any code operation is just used for control flow.

Here's how a switcher it might look like operating. The first column shows the operation performed, and the other two columns showing the value of those variables used for control flow, which are always 0 or 1.

 A  0  0
 A  0  0
 A  0  0
 a  1  0
    0  1
 B  1  0
    0  1
 B  1  0
    0  1
 B  1  0
    0  1
 b  0  0
 A  0  0
 A  0  0
 ...

What is it good for?

So, why do we want a switcher? Well, without a gadget like this, it's hard to keep FRACTRAN focused on a task. Say we want to alternate between doing A repeatedly and doing B repeatedly. FRACTRAN prioritizes the one that's listed first, so if we list A then B, then when doing B, FRACTRAN will keep jumping back to A when it can. Of course, the other order means we just have the same problem with it jumping back to B.

For example, consider this simple program made of two operations:

A = [-2, +1]
B = [+1, -1]

Starting with [2*n, 0], these operations almost work to product [n, 0] but not quite. First, A is applies as long as possible, adding [-2, +1] until we arrive at[0, n]. For example, with n=3, this goes:

        [6, 0]
add A:  [4, 1]
add A:  [2, 2]
add A:  [0, 3]

Now we have [0, n] and want to get [n, 0]. To move n back to the first entry, we want to to keep adding B = [+1, -1]. Since we can't do A at first, the code indeed switches to B, but then things go wrong:

        [0, 3]
add B:  [1, 2]
add B:  [2, 1]
add A:  [0, 2]

Because doing B twice made A applicable again, it never finishes applying B and so doesn't get to [n, 0].

A switcher lets us fix exactly this by keeping the program on task with B, making it alternates between A-mode and B-mode until each respective task is complete and can be done no further. It also let us run additional one-time operations a and b when switching modes.

The Collatz code

This operation of halving is exactly what the Collatz code does on even values. If we ignore the third and fourth columns (which are for odd values) and their rows, we get:

       code switcher
             -1 +1
(B)   +1 -1  +1 -1
(b)             -1
(A)   -2 +1       
(a)   +1 -1  +1  

This is exactly a switcher (in columns 3 and 4) applies to the operations in the first two columns. These are the halving operations A = [-2, +1], B = [+1, -1] described before. A detail is that we also have b = A to make the transition from B work out by doing A an additional time in advance.

Similarly, columns 3 and 4 are a switcher for the operation used for odd values. To take [n,0] -> [3*n+1,0] for odd n, we use:

A = [-2, +1]
a = [-1, -1]
B = [+6, -1]
b = [+10, 0]

Note that making B be [+6, -1] rather than [+1, -1] as for the even case means that we end up with a result about 6 times as big, so 3*n rather than n/2. The a and b work out to give the +1 in 3*n+1 while serving other useful purposes. Specifically, they make the code go into the odd switcher rather than the even switcher when the first entry is odd, as well as make the program terminate when the Collatz sequence reaches 1.

The odd code might be a bit simpler producing (3*n+1)/2, that is pre-doing an addition halving step, which is always what follows because 3*n+1 is even for odd n. But, I think that this would just make the numerical entries in the rows smaller rather than cutting a row (fraction), which is what counts for scoring.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.