anders_collatz_length.txt

This is an analysis of https://codegolf.stackexchange.com/a/203685/78112
like in https://gist.github.com/kmill/266ef6bb5690f9c26110673dcc59f710

Input: n A

1. M1    +      A -> M2 + 10 B
2  M1             -> M2 + A
3. M2  +  A + Div -> M1 + B
4. M2 + 4 B + Div -> M1 + A
5. M2             -> Count
6.              B -> A
7.            2 A -> Div
8.            Div -> M1

Output: A + c Count

Anders's prime assignments:
2  <->  B
3  <->  A
5  <->  M2
7  <->  Div
11 <->  M1
13 <->  Count


Roughly what's going on is the input (as n copies of A) is converted by Eq.7
into Div copies of the quotient A/2, with possibly a lone A if n was odd. Then,
Eq.8 applies if n was bigger than 1, starting up the multiplication loop; this
decrements Div due to the test.  Call k the quotient A/2, hence the state is
now M1 + (k - 1) Div + r A, where r is the remainder after division.

I find these FRACTRAN kernels that Anders devises to be rather clever. In this
case, 
1) If r=0, then evaluation cycles between Eq.2 and Eq.3.  Each Div is converted
   into an A, but Eq.2 will leave an extra A at the end before Eq.5 applies.
   All together, this does M1 + (k - 1) Div -> ... -> Count + A + (k - 1) B.
   Eq.6 then repeatedly applies, resulting in Count + k A.
2) If r=1, then evaluation cycles between Eq.1 and Eq.4.  Each Div is converted
   into 10 - 4 = 6 copies of B, leaving an extra A.  Then, Eq.1 applies once
   more, converting the last A into 10 B, then Eq.5 applies.  All together,
   this does M1 + (k - 1) Div + A -> ... -> Count + 6(k - 1) B + 10 B,
   which is (6k + 4) B, which are then converted back into A's by Eq.6.

Hence, if n was even, n is replaced by n/2, and if n was odd, n is replaced by
6k + 4 = 3(2k + 1) + 1 = 3n + 1.  Also, in either case, there is one more Count.

At the end of the program, the result is A + c Count, with the one A
representing that n=1 was the last case considered by the program before it
halted.

---

Anders must have optimized the prime assignments, since with this program, 45
bytes is optimal:

   '5120/33,15/11,22/105,33/560,13/5,3/2,7/9,11/7'

---

Another 8-fraction program comes from modifying his program from
https://codegolf.stackexchange.com/a/203682/78112

Input: n A

1.            2 Rem -> Div
2. M1     +     Rem -> M2 + 2 A
3. M1     +     Div -> M2 + Rem
4. M2     +     Div -> M1 + A + Rem
5. M2 + Count + Rem -> A
6.               M2 -> 0
7.                A -> Rem
8.              Div -> M1 + 2 Count + 2 Rem

Output: Rem + c Count

The lingering Rem is like in the previous program, where, except for control
flow, A's and Rem's mean the same thing.

See the analysis in https://gist.github.com/kmill/266ef6bb5690f9c26110673dcc59f710
to see how this program works.  The only change is that in Eq.8, two Count's
are created, in case n was odd, since the program divides by 2 immediately
so actually completes two steps, and then Eq.5 removes one of the Counts in
case n was even.  As a trick, the Rem is replaced by an A since FRACTRAN
equations cannot have the same species on each side.

Optimizing the prime assignment for number of bytes in the textual
representation of the FRACTRAN program, it turns out a good assignment is
5  <-> A
11 <-> Count
2  <-> Rem
7  <-> Div
13 <-> M1
3  <-> M2

This gives 41 bytes:

   '7/4,75/26,6/91,130/21,5/66,1/3,2/5,6292/7'