mjhjmtu

Here is a list of rational numbers:

$frac2221, frac711, frac137, frac5165, frac1317, frac113, frac152, frac71$

This list is actually a computer program! It takes an integer as its input, and outputs a sequence of integers. The way it executes is as follows:

Find the first fraction on the list that, when multiplied to the input, produces an integer. That integer is output. The process is then repeated using that integer as the new input.

For example, if the program is run with input $2$, then the output will be the sequence $15, 105, 110, 70, 130, ...$.

When given $2$ as its input, what does this program do?

More specifically, when it produces an integer of the form $2^a 3^b$, what can you say about $a$ and $b$?

Source:

This puzzle is mostly an excuse to show this esoteric, Turing-complete programming language that few people have heard of. I wrote the simple program used in this puzzle myself. The programming language is called FRACTRAN, and it was invented by John Horton Conway.

First, let's change our interpretation of the rational numbers as

Translating some (power of) prime factors from the input to another (power of) prime factors:

$[1]~3,7 rightarrow 2,11$
$[2]~11 rightarrow 7$
$[3]~7 rightarrow 13$
$[4]~5,13 rightarrow 3,17$
$[5]~17 rightarrow 13$
$[6]~13 rightarrow .$
$[7]~2 rightarrow 3,5$
$[8]~. rightarrow 7$

As you may see, if we start with $2^a3^b$

We will always go to $[7]$, translating all $2$ to $3$ and $5$, until there is no $2$ left and we will get $3^a+b5^a$.

Next

We will go to $[8]$ to receive a "token" of $7$.

What's so special about it?

It can be used for $[1]-[3]$.

$[1]$ require the token and a prime factor $3$, generate $2$ and new token $11$.

On $[2]$ the new token will be replaced to original token $7$, so it will go back to $[1]$ until...

There is no $3$ left, and we will go to $[3]$, replace the token to another token of $13$.

Here, we will get

$2^a+b5^a13$, the $3$ were all translated to $2$.

The next part is actually

The same. $[4]-[6]$ is similar with $[1]-[3]$ except it translated $5$ to $3$, and the token will be dissapeared.

Leaving the "final" number

$2^a+b3^a$

Hence

If we let $a$ being the power of $2$ and $b$ being the power of $3$, we will transform $(a,b)$ to $(a+b,a)$. The first number will go to second one, and the sum of them will go to the first one.

This is actually a Fibonacci series with given $(F_n,F_n-1)$ which will be translated to $(F_n+1,F_n)$

It looks like the program calculates

the Fibonacci sequence.

Specifically, the $n$-th time the output sequence is of the form $2^a3^b$,

$a = F_n+1$, $b = F_n$

(the input, 2, counts as $n=0$)

The first few outputs are:

2, 15, 105, 110, 70, 130, 102, 78, 6, 45, 315, 330, 210, 220, 140, 260, 204, 156, 12, ..., 72 (33th output), ..., 864 (55th output), ...

How it does this is a mystery to me ...