Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# kmill/anders_collatz_length.txt

Last active Apr 21, 2020
 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'
to join this conversation on GitHub. Already have an account? Sign in to comment