BusyBeaverWiki - User contributions [en]

Talk:Consistent Collatz

2024-08-12T14:53:04Z

Ais523: another relevant paper

Thank you very much for this interesting contribution !

* Is this wiki entry the first documentation of this work or are there any resources outhere about it (paper, blog, ...)?
* Did you mint the term "consistent Collatz sequence" or was it introduced before in the litterature?
* How do "consistent Collatz sequences" differ from Conway's "generalised Collatz maps"?

Thank you!

:I mostly came up with the terminology myself, because I need to call it something in order to be able to write about it. Although I worked out the results on my own, I'm pretty sure other people got there before me; but I'm not sure whether any of them actually wrote down the theory anywhere (as opposed to simply writing programs that made use of it). Collatz functions (which generalize Collatz problems, and which are what Conway studied) already have a lot of documentation (e.g. https://esolangs.org/wiki/Collatz_function); this article is talking about a special case in which all the multipliers are the same, thus "consistent". (This page uses only a single <math>r</math> value for the entire Collatz function; but Collatz functions in general can have different <math>r</math> values for different values of <math>x\ \textrm{mod}\ m</math>, something which Conway took advantage of when proving the iterated versions to be Turing-complete.) [[User:Ais523|Ais523]] ([[User talk:Ais523|talk]]) 22:54, 5 August 2024 (UTC)

== Some pre-existing research ==

According to [https://oeis.org/A061418 OEIS], the Hydra/Antihydra sequence is (the ceiling of) a multiple of the sequence of powers of 3/2 (although the ratio is hard to compute, and is probably related to the sequence of <math>j</math> in the article) – I suspect that that result generalises to consistent Collatz sequences in general, although I haven't proved it. There are some known results about real multiples of sequences of powers of rationals in [[doi:10.4064/aa-70-2-125-147|this paper]] and [[doi:10.1016/j.jnt.2005.07.004|this paper]], but unfortunately AFAICT they aren't strong enough to prove any of the results we care about. [[User:Ais523|Ais523]] ([[User talk:Ais523|talk]]) 14:31, 12 August 2024 (UTC)

Talk:Consistent Collatz

2024-08-12T14:33:38Z

Ais523: actually, link the paper by DOI, to reduce the chance the link breaks

Thank you very much for this interesting contribution !

* Is this wiki entry the first documentation of this work or are there any resources outhere about it (paper, blog, ...)?
* Did you mint the term "consistent Collatz sequence" or was it introduced before in the litterature?
* How do "consistent Collatz sequences" differ from Conway's "generalised Collatz maps"?

Thank you!

:I mostly came up with the terminology myself, because I need to call it something in order to be able to write about it. Although I worked out the results on my own, I'm pretty sure other people got there before me; but I'm not sure whether any of them actually wrote down the theory anywhere (as opposed to simply writing programs that made use of it). Collatz functions (which generalize Collatz problems, and which are what Conway studied) already have a lot of documentation (e.g. https://esolangs.org/wiki/Collatz_function); this article is talking about a special case in which all the multipliers are the same, thus "consistent". (This page uses only a single <math>r</math> value for the entire Collatz function; but Collatz functions in general can have different <math>r</math> values for different values of <math>x\ \textrm{mod}\ m</math>, something which Conway took advantage of when proving the iterated versions to be Turing-complete.) [[User:Ais523|Ais523]] ([[User talk:Ais523|talk]]) 22:54, 5 August 2024 (UTC)

== Some pre-existing research ==

According to [https://oeis.org/A061418 OEIS], the Hydra/Antihydra sequence is (the ceiling of) a multiple of the sequence of powers of 3/2 (although the ratio is hard to compute, and is probably related to the sequence of <math>j</math> in the article) – I suspect that that result generalises to consistent Collatz sequences in general, although I haven't proved it. There are some known results about real multiples of sequences of powers of rationals in [[doi:10.4064/aa-70-2-125-147|this paper]], but unfortunately AFAICT they aren't strong enough to prove any of the results we care about. [[User:Ais523|Ais523]] ([[User talk:Ais523|talk]]) 14:31, 12 August 2024 (UTC)

Talk:Consistent Collatz

2024-08-12T14:31:10Z

Ais523: /* Some pre-existing research */ new section

Thank you very much for this interesting contribution !

* Is this wiki entry the first documentation of this work or are there any resources outhere about it (paper, blog, ...)?
* Did you mint the term "consistent Collatz sequence" or was it introduced before in the litterature?
* How do "consistent Collatz sequences" differ from Conway's "generalised Collatz maps"?

Thank you!

:I mostly came up with the terminology myself, because I need to call it something in order to be able to write about it. Although I worked out the results on my own, I'm pretty sure other people got there before me; but I'm not sure whether any of them actually wrote down the theory anywhere (as opposed to simply writing programs that made use of it). Collatz functions (which generalize Collatz problems, and which are what Conway studied) already have a lot of documentation (e.g. https://esolangs.org/wiki/Collatz_function); this article is talking about a special case in which all the multipliers are the same, thus "consistent". (This page uses only a single <math>r</math> value for the entire Collatz function; but Collatz functions in general can have different <math>r</math> values for different values of <math>x\ \textrm{mod}\ m</math>, something which Conway took advantage of when proving the iterated versions to be Turing-complete.) [[User:Ais523|Ais523]] ([[User talk:Ais523|talk]]) 22:54, 5 August 2024 (UTC)

== Some pre-existing research ==

According to [https://oeis.org/A061418 OEIS], the Hydra/Antihydra sequence is (the ceiling of) a multiple of the sequence of powers of 3/2 (although the ratio is hard to compute, and is probably related to the sequence of <math>j</math> in the article) – I suspect that that result generalises to consistent Collatz sequences in general, although I haven't proved it. There are some known results about real multiples of sequences of powers of rationals in [http://matwbn.icm.edu.pl/ksiazki/aa/aa70/aa7023.pdf this paper], but unfortunately AFAICT they aren't strong enough to prove any of the results we care about. [[User:Ais523|Ais523]] ([[User talk:Ais523|talk]]) 14:31, 12 August 2024 (UTC)

Consistent Collatz

2024-08-05T22:59:34Z

Ais523: clarify the relationship to generalized Collatz functions

A '''consistent Collatz''' sequence is a sequence of integers which can be defined by a recurrence relation of the following form:

<math>mx_{n+1} = rx_n + J[x_n\ \textrm{mod}\ m]</math>

where the sequence itself is <math>x_0, x_1, \ldots</math>, <math>m</math> and <math>r</math> are positive integers, and <math>J</math> is a map from integers modulo <math>m</math> to (possibly negative) integers (with the values chosen to ensure that all <math>x_n</math> are integers). The sequence is entirely defined by <math>m</math>, <math>r</math>, <math>J</math>, and the value of its first element <math>x_0</math>. The recurrence relation is a special case of a Collatz function (e.g. as seen in [[wikipedia:Collatz conjecture#Undecidable generalizations]]) in which all the multipliers are the same (i.e. the same value of <math>r</math> is used regardless of the value of <math>x_n\ \textrm{mod}\ m</math>).

Many small [[cryptids]] work by calculating the elements of a consistent Collatz sequence modulo <math>m</math>, and deciding whether or not to halt based on the remainders. For example, [[Hydra]] calculates the consistent Collatz sequence with <math>m=2</math>, <math>r=3</math>, <math>J=\{0 \mapsto 0, 1 \mapsto -1\}</math>, and <math>x_0=3</math>, halting only if the sequence has contained more than twice as many even elements as odd elements. <math>m=2, r=3</math> seems to be particularly common among small cryptids, due to creating the simplest consistent Collatz sequences that have nontrivial behaviour; however, other values have been observed, such as [[Bigfoot]]'s <math>m=81, r=256</math>.

== Efficiently calculating consistent Collatz sequences ==

For any given Collatz sequence, it is possible to calculate its sequence of remainders <math>x_n\ \textrm{mod}\ m</math> in amortized [[wikipedia:quasilinear time|quasilinear time]]. This can be accomplished via the use of two helper sequences:

<math>w_n = x_n\ \textrm{mod}\ m^{f(n)}</math>, except <math>w_0 = x_0</math> 
<math>j_n = m^{f(n)}x_n - r^{f(n)}x_{n-f(n)}</math>, with <math>j_0</math> undefined (the algorithm never uses it)

where <math>f(n)</math> is the largest power of 2 that divides into <math>n</math>.

=== Time complexity ===

The algorithm works by calculating <math>j_n</math> then <math>w_n</math> for each <math>n</math> in turn, with the only operations used being additions, subtractions, and multiplications of numbers whose number of digits is proportional to <math>f(n)</math>; division and modulo by powers of <math>m</math>; and calculation of <math>r^t</math> with <math>t \leq f(n)</math>. Because the values of <math>r^t</math> can be memoized, and it is possible to trivialise the division and modulus operations by storing the numbers in base <math>m</math>, this means that the only slow operations are additions and subtractions taking <math>O(f(n))</math> time, and multiplications taking <math>O(f(n) \log f(n) \log \log f(n))</math> time (and there are <math>O(\log f(n))</math> such operations performed), so the calculation of each <math>w_n, j_n</math> pair takes time quasilinear in <math>f(n)</math>. <math>\Sigma_{t=1}^n{f(t)}=O(n \log n)</math>: as such, the calculation of the entire sequences <math>w_0, \ldots, w_n</math> and <math>j_0, \ldots, j_n</math> takes time quasilinear in <math>n \log n</math>, thus quasilinear in <math>n</math>.

=== Details of the algorithm ===

The algorithm itself is:

<math>j_n = m^{f(n)-1} J[w_{n-1}\ \textrm{mod}\ m] + \Sigma_{e=1}^{\log_2 f(n)}\left(m^{f(n)-2^e}r^{2^{e-1}}j_{n-2^{e-1}}\right)</math> 
<math>w'_n = j_n + r^{f(n)} w_{n-f(n)} \mod m^{2f(n)}</math> (i.e. all the calculations are done modulo <math>m^{2f(n)}</math>, saving time in cases where <math>w_{n-f(n)}</math> happens to be much larger than <math>m^{2f(n)}</math>) 
<math>w_n = w'_n \div m^{f(n)}</math> (which should always be an integer).

(If <math>n</math> is odd, then <math>f(n) = 1</math>, <math>\log_2 f(n) = 0</math>, and the sum in the calculation of <math>j_n</math> is a degenerate sum with no elements.)

=== Sketch proof of correctness ===

The proof that the algorithm is correct starts with the definition <math>j_n = m^{f(n)}x_n - r^{f(n)}x_{n-f(n)}</math>, adds a degenerate sum (that sums to zero) to produce the following expression:

<math>j_n = m^{f(n)}x_n + \Sigma_{e=1}^{\log_2 f(n)}\left(-m^{f(n)-2^{e-1}}r^{2^{e-1}}x_{n-2^{e-1}}+m^{f(n)-2^{e-1}}r^{2^{e-1}}x_{n-2^{e-1}}\right) - r^{f(n)}x_{n-f(n)}</math> (with each element of the sum being of the form <math>-q+q</math> and thus 0)

and then rebrackets by grouping the term before the sum with the first half of the first element of the sum, the second half of the first element of the sum with the first half of the second element of the sum, etc., and finally the second half of the last element of the sum with the term after the sum. From there, the proof is mostly just a matter of expanding definitions.

=== Possible tricks to optimize the implementation ===

Once the algorithm produces a value of <math>j_n</math> or <math>w_n</math>, it happens that it will never again read a value <math>j_{n'}</math> or <math>w_{n'}</math> where <math>f(n)=f(n')</math>. As such, it is possible to save memory by storing only one value of <math>j_n</math> and one value of <math>w_n</math> for each <math>f(n)</math>.

It is probably faster to switch to an alternative implementation (e.g. simple repeated multiplication) when the <math>f(n)</math> values are small, because at that point the numbers are small enough to fit into a machine register; this does not improve the asymptotic behaviour of the implementation but is likely to speed it up by a reasonably high constant factor.

Every <math>w'_n</math> is necessarily a multiple of <math>m^{f(n)}</math>. It seems like that might provide some sort of shortcut to calculate it faster, although the details are currently unclear.

=== Proof-of-concept implementation ===

Here's a proof-of-concept implementation, using Python 3 and gmpy2 (configured to calculate [[Hydra]], but it could easily be adapted for other consistent Collatz sequences with <math>m=2</math>):

<syntaxhighlight lang="python3">
import gmpy2
import time

# The Rules of Hydra:
# if x_n = 2y + 0, then x_{n+1} = 3y + 0, i.e. 2x_{n+1} = 3x_n + 0
# if x_n = 2y + 1, then x_{n+1} = 3y + 1, i.e. 2x_{n+1} = 3x_n - 1
m = 2 # modulus; denominator of the ratio between successive elements
r = 3 # numerator of the ratio between successive elements
J = [0, -1] # J[x_n % m] is the difference between m*x_{n+1} and r*x_n
x_0 = 3 # first term of the sequence

def f(n):
"""The largest power of 2 that divides into the argument"""
return n & ~(n - 1)

global mod_m_exp
if m == 2:
mod_m_exp = lambda v,e: gmpy2.f_mod_2exp(v, e)
else:
mod_m_exp = lambda v,e: gmpy2.f_mod(v, gmpy2.pow(m, e))

global div_m_exp
if m == 2:
div_m_exp = lambda v,e: gmpy2.f_div_2exp(v, e)
else:
div_m_exp = lambda v,e: gmpy2.f_div(v, gmpy2.pow(m, e))

global mul_m_exp
if m == 2:
mul_m_exp = lambda v,e: gmpy2.mpz(v) << e
else:
mul_m_exp = lambda v,e: gmpy2.mul(v, gmpy2.pow(m, e))

r_exp_cache = {1: gmpy2.mpz(r)}
def r_exp(e):
"""Returns r raised to the power of e. e must be a power of 2."""
global r_exp_cache
if not e in r_exp_cache:
r_exp_cache[e] = gmpy2.square(r_exp(e/2))
return r_exp_cache[e]

# The bulk of the calculation is to calculate w_n and j_n for each n.
# The definitions are:
# w_n = x_n mod m**f(n)
# j_n = m**f(n) * x_n - r**f(n) * x_{n-f(n)}
# The output from the program is the sequence of x_n mod m.
# This can be calculated by taking the values of w_n mod m.
w = {0: x_0} # most recently seen w for each f value
j = {} # most recently seen j for each f value

modulus_count = {0: 0, 1: 0}

n = 0
perf_counter_timestamp = time.perf_counter_ns()
while True:
last_f = f(n)
last_x_mod_m = mod_m_exp(w[last_f], 1)
# print(last_x_mod_m, end="")

modulus_count[last_x_mod_m] += 1
if n % 1000000 == 0:
last_timestamp = perf_counter_timestamp
perf_counter_timestamp = time.perf_counter_ns()
print("Reached n = ", n, "; modulus counts: ", modulus_count,
"; time for last 1000000 elements = ",
(perf_counter_timestamp - last_timestamp) // 1000000,
" ms", sep="")

n = n + 1
cur_f = f(n)

# j can be a sum of multiple terms; J[last_x_mod_m] is always present
# but if f > 1 there are other terms too
m_shift = cur_f - 1
r_shift = 1
new_j = mul_m_exp(J[last_x_mod_m], m_shift)
while m_shift >= r_shift:
m_shift -= r_shift
new_j += mul_m_exp(j[r_shift] * r_exp(r_shift), m_shift)
r_shift *= 2
j[cur_f] = new_j

# w can be calculated directly from the new j and the appropriate past w
wrap = lambda v: mod_m_exp(v, cur_f * 2)
past_w = w[f(n - f(n))]
new_w = wrap(wrap(new_j) + wrap(wrap(r_exp(cur_f)) * wrap(past_w)))
assert(mod_m_exp(new_w, cur_f) == 0)
new_w = div_m_exp(new_w, cur_f)
w[cur_f] = new_w
</syntaxhighlight>

This implementation is probably not suitable for serious use due to having poor constant factors: a faster implementation would use an alternative algorithm for low <math>f(n)</math> values. It is also intened only for <math>m=2</math>, because the complexity result is dependent on modulus by powers of <math>m</math> being fast regardless of the size of the dividend, but gmpy2 is only able to store numbers in binary and that operation is quick only if the modulus is a power of the base. As such, a full implementation of efficient consistent Collatz calculation would probably involve writing a new arbitrarily-large-integers library which is able to store numbers in arbitrary bases.

Talk:Consistent Collatz

2024-08-05T22:54:22Z

Ais523: replies

Antihydra

2024-08-04T00:37:48Z

Ais523: this uses a consistent Collatz sequence, which makes it possible to simulate efficiently

{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}{{unsolved|Does Antihydra run forever?}}
[[File:Antihydra-depiction.png|right|thumb|Artistic depiction of Antihydra by Jadeix]]
'''Antihydra''' is the 6-state 2-symbol machine {{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}.

This machine was the first identified [[BB(6)]] Collatz-like [[Cryptid]], and is closely related to [[Hydra]].

It simulates the Collatz-like iteration

<math display="block">\begin{array}{l}
A(2a, & b) & \to & A(3a, & b+2) \\
A(2a+1, & b) & \to & A(3a+1, & b-1) & \text{if} & b>0 \\
A(2a+1, & 0) & \to & \text{HALT}
\end{array}</math>
 
starting from <math>A(8, 0)</math>, using configurations of the form <math>A(a+4, b) = 0^\infty \; 1^b \; 0 \; 1^a \; E> \; 0^\infty</math>.<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>

It was discovered by mxdys on 28 Jun 2024 and shared on Discord.<ref>[https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 Discord message], accessed 30 June 2024.</ref>

Racheline found that compared to the [[Hydra]] iteration, this one starts at (8, 0) rather than (3, 0), and the roles of odd and even a are exchanged (in terms of which increases b by two, and which decrements b or halts).
Obstacles to proving the long-run behavior are equally serious.
Like the [[Hydra]] iteration, this one is biased toward increasing the value of b (assuming equal chances of adding +2 or -1).

There is no halt in the first 11.8 million iterations, by which point b has reached 5890334 (which means that it also does not halt in the first 17690334 iterations).<ref>[https://discord.com/channels/960643023006490684/1026577255754903572/1256403772998029372 Discord message], accessed 2 July 2024.</ref>

== Simulator ==

Antihydra is based on a [[consistent Collatz]] sequence, and as such, its behaviour can be simulated efficiently via using the techniques written in that article.

Two older simulators are available (that are much slower for calculating large numbers of elements due to running in <math>O(n^2)</math> rather than quasilinear time, but may be useful in cases where more detail is needed about each element or where only a relatively small number of elements is needed):

A fast simulator written in Rust for the odd/even sequence used by Antihydra is available [http://nethack4.org/esolangs/fasthydra.zip here].

Alternatively, here is a GMP implementation of the program with some performance diagnostics added:<syntaxhighlight lang="c">
/* Tested on GMP 6.3.0, Ubuntu 24.04. */

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>

#include <gmp.h>

static uint64_t get_milis(void) {
struct timespec ts;
timespec_get(&ts, TIME_UTC);
return (uint64_t)(ts.tv_sec * 1000 + ts.tv_nsec/1000000);
}

int main(int argc, char **argv) {
char *as, *bs;
mpz_t a, aq, ar, b;
uint64_t i, time, newtime;

/* CLI and init. */
if (argc > 1) {
as = argv[1];
} else {
as = "8";
}
if (argc > 2) {
bs = argv[2];
} else {
bs = "0";
}
mpz_init_set_str(a, as, 10);
mpz_init_set_str(b, bs, 10);
mpz_init(aq);
mpz_init(ar);
i = 0;
time = get_milis();

/* Run. */
while (1) {
/* aq = a / 2
* ar = a % 2 */
mpz_fdiv_qr_ui(aq, ar, a, 2);
if (
/* odd */
mpz_cmp_ui(ar, 0)
) {
if (!mpz_cmp_ui(b, 0)) break;
/* a = aq * 3 + 1 */
mpz_mul_ui(a, aq, 3);
mpz_add_ui(a, a, 1);
/* b -= 1 */
mpz_sub_ui(b, b, 1);
} else {
/* a = aq * 3 */
mpz_mul_ui(a, aq, 3);
/* b += 2 */
mpz_add_ui(b, b, 2);
}
i++;
if (i % 100000 == 0) {
newtime = get_milis();
gmp_printf("%" PRIu64 " ms=%" PRIu64 " log10(a)=%ju log10(b)=%ju\n",
i/100000, newtime - time, mpz_sizeinbase(a, 10), mpz_sizeinbase(b, 10));
time = newtime;
}
}

/* Cleanup if we ever reach it. */
mpz_clear(a);
mpz_clear(aq);
mpz_clear(ar);
mpz_clear(b);
return 0;
}‎</syntaxhighlight>

Compile and run with:<syntaxhighlight lang="bash">
gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out‎</syntaxhighlight>

Tested on Tested on GMP 6.3.0, Ubuntu 24.04.

==Sources==
<references />

[[Category:Individual machines]]

Hydra

2024-08-04T00:30:58Z

Ais523: the Hydra sequence can be calculated quickly due to being a consistent Collatz sequence

{{machine|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved|Does Hydra run forever?}}{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}
'''Hydra''' is a [[BB(2,5)]] machine that simulates the Collatz-like iteration

<math display="block">\begin{array}{l}
C(2a+1, & b) & \to & A(3a+1, & b+2) \\
C(2a, & b) & \to & A(3a, & b-1) & \text{if} & b>0 \\
C(2a, & 0) & \to & \text{HALT}
\end{array}</math>
 
starting from <math>C(3,0)</math>, using configurations of the form <math>C(a+2,b) = 0^\infty \; .<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2023). Accessed 22 July 2024.</ref>

It is closely related to the machine [[Antihydra]].<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>

The sequence calculated by Hydra is a [[consistent Collatz]] sequence, (which implies, among other things, that its odd/even pattern can be calculated in quasilinear time). In the first 60 million elements, there are 29995836 even values of <code>a</code> and 30004165 odd values; thus, is known that Hydra cannot halt within the first 90 million Collatz iterations.

An older simulator for the odd/even sequence used by Hydra is available [http://nethack4.org/esolangs/fasthydra.zip here], but it runs in <math>O(n^2)</math> time and thus is unusably slow compared to the consistent Collatz simulation approach.

== Name ==

The name ''Hydra'' references the Ancient Greek legend: just as the legendary creature was growing 2 heads after losing 1 head, the ''b'' counter that is kept on the right side of the tape either increases by 2 or decreases by 1 (approximately with equal frequency if modelled as a random process; in reality it depends on the parity of ''a''). The Hydra dies (halts) when the last head is cut.

==Sources==
<references/>

[[Category:Stub]]

Consistent Collatz

2024-08-04T00:25:43Z

Ais523: a class of sequences, including that used by Hydra/Antihydra, that can be calculated in quasilinear time

A '''consistent Collatz''' sequence is a sequence of integers which can be defined by a recurrence relation of the following form:

<math>mx_{n+1} = rx_n + J[x_n\ \textrm{mod}\ m]</math>

where the sequence itself is <math>x_0, x_1, \ldots</math>, <math>m</math> and <math>r</math> are positive integers, and <math>J</math> is a map from integers modulo <math>m</math> to (possibly negative) integers (with the values chosen to ensure that all <math>x_n</math> are integers). The sequence is entirely defined by <math>m</math>, <math>r</math>, <math>J</math>, and the value of its first element <math>x_0</math>.

Many small [[cryptids]] work by calculating the elements of a consistent Collatz sequence modulo <math>m</math>, and deciding whether or not to halt based on the remainders. For example, [[Hydra]] calculates the consistent Collatz sequence with <math>m=2</math>, <math>r=3</math>, <math>J=\{0 \mapsto 0, 1 \mapsto -1\}</math>, and <math>x_0=3</math>, halting only if the sequence has contained more than twice as many even elements as odd elements. <math>m=2, r=3</math> seems to be particularly common among small cryptids, due to creating the simplest consistent Collatz sequences that have nontrivial behaviour; however, other values have been observed, such as [[Bigfoot]]'s <math>m=81, r=256</math>.

== Efficiently calculating consistent Collatz sequences ==

For any given Collatz sequence, it is possible to calculate its sequence of remainders <math>x_n\ \textrm{mod}\ m</math> in amortized [[wikipedia:quasilinear time|quasilinear time]]. This can be accomplished via the use of two helper sequences:

<math>w_n = x_n\ \textrm{mod}\ m^{f(n)}</math>, except <math>w_0 = x_0</math> 
<math>j_n = m^{f(n)}x_n - r^{f(n)}x_{n-f(n)}</math>, with <math>j_0</math> undefined (the algorithm never uses it)

where <math>f(n)</math> is the largest power of 2 that divides into <math>n</math>.

=== Time complexity ===

The algorithm works by calculating <math>j_n</math> then <math>w_n</math> for each <math>n</math> in turn, with the only operations used being additions, subtractions, and multiplications of numbers whose number of digits is proportional to <math>f(n)</math>; division and modulo by powers of <math>m</math>; and calculation of <math>r^t</math> with <math>t \leq f(n)</math>. Because the values of <math>r^t</math> can be memoized, and it is possible to trivialise the division and modulus operations by storing the numbers in base <math>m</math>, this means that the only slow operations are additions and subtractions taking <math>O(f(n))</math> time, and multiplications taking <math>O(f(n) \log f(n) \log \log f(n))</math> time (and there are <math>O(\log f(n))</math> such operations performed), so the calculation of each <math>w_n, j_n</math> pair takes time quasilinear in <math>f(n)</math>. <math>\Sigma_{t=1}^n{f(t)}=O(n \log n)</math>: as such, the calculation of the entire sequences <math>w_0, \ldots, w_n</math> and <math>j_0, \ldots, j_n</math> takes time quasilinear in <math>n \log n</math>, thus quasilinear in <math>n</math>.

=== Details of the algorithm ===

The algorithm itself is:

<math>j_n = m^{f(n)-1} J[w_{n-1}\ \textrm{mod}\ m] + \Sigma_{e=1}^{\log_2 f(n)}\left(m^{f(n)-2^e}r^{2^{e-1}}j_{n-2^{e-1}}\right)</math> 
<math>w'_n = j_n + r^{f(n)} w_{n-f(n)} \mod m^{2f(n)}</math> (i.e. all the calculations are done modulo <math>m^{2f(n)}</math>, saving time in cases where <math>w_{n-f(n)}</math> happens to be much larger than <math>m^{2f(n)}</math>) 
<math>w_n = w'_n \div m^{f(n)}</math> (which should always be an integer).

(If <math>n</math> is odd, then <math>f(n) = 1</math>, <math>\log_2 f(n) = 0</math>, and the sum in the calculation of <math>j_n</math> is a degenerate sum with no elements.)

=== Sketch proof of correctness ===

The proof that the algorithm is correct starts with the definition <math>j_n = m^{f(n)}x_n - r^{f(n)}x_{n-f(n)}</math>, adds a degenerate sum (that sums to zero) to produce the following expression:

<math>j_n = m^{f(n)}x_n + \Sigma_{e=1}^{\log_2 f(n)}\left(-m^{f(n)-2^{e-1}}r^{2^{e-1}}x_{n-2^{e-1}}+m^{f(n)-2^{e-1}}r^{2^{e-1}}x_{n-2^{e-1}}\right) - r^{f(n)}x_{n-f(n)}</math> (with each element of the sum being of the form <math>-q+q</math> and thus 0)

and then rebrackets by grouping the term before the sum with the first half of the first element of the sum, the second half of the first element of the sum with the first half of the second element of the sum, etc., and finally the second half of the last element of the sum with the term after the sum. From there, the proof is mostly just a matter of expanding definitions.

=== Possible tricks to optimize the implementation ===

Once the algorithm produces a value of <math>j_n</math> or <math>w_n</math>, it happens that it will never again read a value <math>j_{n'}</math> or <math>w_{n'}</math> where <math>f(n)=f(n')</math>. As such, it is possible to save memory by storing only one value of <math>j_n</math> and one value of <math>w_n</math> for each <math>f(n)</math>.

It is probably faster to switch to an alternative implementation (e.g. simple repeated multiplication) when the <math>f(n)</math> values are small, because at that point the numbers are small enough to fit into a machine register; this does not improve the asymptotic behaviour of the implementation but is likely to speed it up by a reasonably high constant factor.

Every <math>w'_n</math> is necessarily a multiple of <math>m^{f(n)}</math>. It seems like that might provide some sort of shortcut to calculate it faster, although the details are currently unclear.

=== Proof-of-concept implementation ===

Here's a proof-of-concept implementation, using Python 3 and gmpy2 (configured to calculate [[Hydra]], but it could easily be adapted for other consistent Collatz sequences with <math>m=2</math>):

<syntaxhighlight lang="python3">
import gmpy2
import time

# The Rules of Hydra:
# if x_n = 2y + 0, then x_{n+1} = 3y + 0, i.e. 2x_{n+1} = 3x_n + 0
# if x_n = 2y + 1, then x_{n+1} = 3y + 1, i.e. 2x_{n+1} = 3x_n - 1
m = 2 # modulus; denominator of the ratio between successive elements
r = 3 # numerator of the ratio between successive elements
J = [0, -1] # J[x_n % m] is the difference between m*x_{n+1} and r*x_n
x_0 = 3 # first term of the sequence

def f(n):
"""The largest power of 2 that divides into the argument"""
return n & ~(n - 1)

global mod_m_exp
if m == 2:
mod_m_exp = lambda v,e: gmpy2.f_mod_2exp(v, e)
else:
mod_m_exp = lambda v,e: gmpy2.f_mod(v, gmpy2.pow(m, e))

global div_m_exp
if m == 2:
div_m_exp = lambda v,e: gmpy2.f_div_2exp(v, e)
else:
div_m_exp = lambda v,e: gmpy2.f_div(v, gmpy2.pow(m, e))

global mul_m_exp
if m == 2:
mul_m_exp = lambda v,e: gmpy2.mpz(v) << e
else:
mul_m_exp = lambda v,e: gmpy2.mul(v, gmpy2.pow(m, e))

r_exp_cache = {1: gmpy2.mpz(r)}
def r_exp(e):
"""Returns r raised to the power of e. e must be a power of 2."""
global r_exp_cache
if not e in r_exp_cache:
r_exp_cache[e] = gmpy2.square(r_exp(e/2))
return r_exp_cache[e]

# The bulk of the calculation is to calculate w_n and j_n for each n.
# The definitions are:
# w_n = x_n mod m**f(n)
# j_n = m**f(n) * x_n - r**f(n) * x_{n-f(n)}
# The output from the program is the sequence of x_n mod m.
# This can be calculated by taking the values of w_n mod m.
w = {0: x_0} # most recently seen w for each f value
j = {} # most recently seen j for each f value

modulus_count = {0: 0, 1: 0}

n = 0
perf_counter_timestamp = time.perf_counter_ns()
while True:
last_f = f(n)
last_x_mod_m = mod_m_exp(w[last_f], 1)
# print(last_x_mod_m, end="")

modulus_count[last_x_mod_m] += 1
if n % 1000000 == 0:
last_timestamp = perf_counter_timestamp
perf_counter_timestamp = time.perf_counter_ns()
print("Reached n = ", n, "; modulus counts: ", modulus_count,
"; time for last 1000000 elements = ",
(perf_counter_timestamp - last_timestamp) // 1000000,
" ms", sep="")

n = n + 1
cur_f = f(n)

# j can be a sum of multiple terms; J[last_x_mod_m] is always present
# but if f > 1 there are other terms too
m_shift = cur_f - 1
r_shift = 1
new_j = mul_m_exp(J[last_x_mod_m], m_shift)
while m_shift >= r_shift:
m_shift -= r_shift
new_j += mul_m_exp(j[r_shift] * r_exp(r_shift), m_shift)
r_shift *= 2
j[cur_f] = new_j

# w can be calculated directly from the new j and the appropriate past w
wrap = lambda v: mod_m_exp(v, cur_f * 2)
past_w = w[f(n - f(n))]
new_w = wrap(wrap(new_j) + wrap(wrap(r_exp(cur_f)) * wrap(past_w)))
assert(mod_m_exp(new_w, cur_f) == 0)
new_w = div_m_exp(new_w, cur_f)
w[cur_f] = new_w
</syntaxhighlight>

This implementation is probably not suitable for serious use due to having poor constant factors: a faster implementation would use an alternative algorithm for low <math>f(n)</math> values. It is also intened only for <math>m=2</math>, because the complexity result is dependent on modulus by powers of <math>m</math> being fast regardless of the size of the dividend, but gmpy2 is only able to store numbers in binary and that operation is quick only if the modulus is a power of the base. As such, a full implementation of efficient consistent Collatz calculation would probably involve writing a new arbitrarily-large-integers library which is able to store numbers in arbitrary bases.

Antihydra

2024-07-21T17:27:50Z

Ais523: another Antihydra simulator I wrote, which is probably faster than the one on the page

{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}
[[File:Antihydra-depiction.png|right|thumb|Artistic depiction of Antihydra by Jadeix]]
Antihydra is the 6-state 2-symbol machine {{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}.

This machine was the first identified [[BB(6)]] Collatz-like [[Cryptid]], and is closely related to [[Hydra]].

It simulates the Collatz-like iteration

<math display="block">\begin{array}{l}
A(2a, & b) & \to & A(3a, & b+2) \\
A(2a+1, & b) & \to & A(3a+1, & b-1) & \text{if} & b>0 \\
A(2a+1, & 0) & \to & \text{HALT}
\end{array}</math>
 
starting from A(8, 0),
 
using configurations of the form <math>A(a+4, b) = 0^\infty \; 1^b \; 0 \; 1^a \; E> \; 0^\infty</math>

It was discovered by mxdys on 28 Jun 2024 and shared on Discord [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318].

Racheline found that compared to the [[Hydra]] iteration, this one starts at (8, 0) rather than (3, 0), and the roles of odd and even a are exchanged (in terms of which increases b by two, and which decrements b or halts).
Obstacles to proving the long-run behavior are equally serious.
Like the [[Hydra]] iteration, this one is biased toward increasing the value of b (assuming equal chances of adding +2 or -1).

There is no halt in the first 11.8 million iterations, by which point b has reached 5890334 (which means that it also does not halt in the first 17690334 iterations) [https://discord.com/channels/960643023006490684/1026577255754903572/1256403772998029372].

== Simulator ==

Two simulators are available. A fast simulator written in Rust for the odd/even sequence used by Antihydra is available [http://nethack4.org/esolangs/fasthydra.zip here].

Alternatively, here is a GMP implementation of the program with some performance diagnostics added:<syntaxhighlight lang="c">
/* Tested on GMP 6.3.0, Ubuntu 24.04. */

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>

#include <gmp.h>

static uint64_t get_milis(void) {
struct timespec ts;
timespec_get(&ts, TIME_UTC);
return (uint64_t)(ts.tv_sec * 1000 + ts.tv_nsec/1000000);
}

int main(int argc, char **argv) {
char *as, *bs;
mpz_t a, aq, ar, b;
uint64_t i, time, newtime;

/* CLI and init. */
if (argc > 1) {
as = argv[1];
} else {
as = "8";
}
if (argc > 2) {
bs = argv[2];
} else {
bs = "0";
}
mpz_init_set_str(a, as, 10);
mpz_init_set_str(b, bs, 10);
mpz_init(aq);
mpz_init(ar);
i = 0;
time = get_milis();

/* Run. */
while (1) {
/* aq = a / 2
* ar = a % 2 */
mpz_fdiv_qr_ui(aq, ar, a, 2);
if (
/* odd */
mpz_cmp_ui(ar, 0)
) {
if (!mpz_cmp_ui(b, 0)) break;
/* a = aq * 3 + 1 */
mpz_mul_ui(a, aq, 3);
mpz_add_ui(a, a, 1);
/* b -= 1 */
mpz_sub_ui(b, b, 1);
} else {
/* a = aq * 3 */
mpz_mul_ui(a, aq, 3);
/* b += 2 */
mpz_add_ui(b, b, 2);
}
i++;
if (i % 100000 == 0) {
newtime = get_milis();
gmp_printf("%" PRIu64 " ms=%" PRIu64 " log10(a)=%ju log10(b)=%ju\n",
i/100000, newtime - time, mpz_sizeinbase(a, 10), mpz_sizeinbase(b, 10));
time = newtime;
}
}

/* Cleanup if we ever reach it. */
mpz_clear(a);
mpz_clear(aq);
mpz_clear(ar);
mpz_clear(b);
return 0;
}
‎</syntaxhighlight>

Compile and run with:<syntaxhighlight lang="bash">
gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out
‎</syntaxhighlight>

Tested on Tested on GMP 6.3.0, Ubuntu 24.04.
[[Category:Individual machines]]

Hydra

2024-07-21T17:26:13Z

Ais523: simulator for Hydra/Antihydra's odd/even sequence

{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}

https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html

A fast simulator for the odd/even sequence used by Hydra is available [http://nethack4.org/esolangs/fasthydra.zip here].

[[Category:Stub]]