Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment