Consistent Collatz - Revision history

Polygon: Linked piecewise affine function

2026-04-27T14:50:21Z

Linked piecewise affine function

← Older revision		Revision as of 14:50, 27 April 2026
Line 1:		Line 1:
	A '''consistent Collatz''' function is a [[Generalized Collatz Function]] (GCF) with the same coefficient in each piecewise affine function. In other words, it is a function <math>g: \mathbb{N} \to \mathbb{N}</math> defined as:		A '''consistent Collatz''' function is a [[Generalized Collatz Function]] (GCF) with the same coefficient in each [[Piecewise Affine Function\|piecewise affine function]]. In other words, it is a function <math>g: \mathbb{N} \to \mathbb{N}</math> defined as:

	<math display="block">g(x) = \begin{cases}		<math display="block">g(x) = \begin{cases}

Polygon: Added Category:Functions

2026-03-31T10:52:54Z

Added Category:Functions

← Older revision		Revision as of 10:52, 31 March 2026
Line 152:		Line 152:

	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.		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.

			[[Category:Functions]]

Sligocki: Update lede to refer to GCF

2025-10-28T18:30:55Z

Update lede to refer to GCF

← Older revision		Revision as of 18:30, 28 October 2025
Line 1:		Line 1:
	A '''consistent Collatz''' ~~sequence~~ is a [[Collatz~~-like~~]] sequence of ~~integers~~ which can be defined by a recurrence relation of the following form:		A '''consistent Collatz''' function is a [[Generalized Collatz Function]] (GCF) with the same coefficient in each piecewise affine function. In other words, it is a function <math>g: \mathbb{N} \to \mathbb{N}</math> defined as:

			<math display="block">g(x) = \begin{cases}
			a x + b_0 & \text{if } x \equiv 0 \pmod{m} \\
			a x + b_1 & \text{if } x \equiv 1 \pmod{m} \\
			& \vdots \\
			a x + b_{m-1} & \text{if } x \equiv m-1 \pmod{m} \\
			\end{cases}</math>

			A consistent Collatz sequence is a sequence of values obtained by iterating a consistent Collatz function: <math>x_{n+1} = g(x_n)</math> which can alternatively be defined by a recurrence relation of the following form:

	<math>mx_{n+1} = rx_n + J[x_n\ {\operatorname{mod}}\ m]</math>		<math>mx_{n+1} = rx_n + J[x_n\ {\operatorname{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<!-- does negative r work too?-->, 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\ {\operatorname{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<!-- does negative r work too?-->, 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>.		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>.

MrSolis: 0_o

2025-10-07T23:21:13Z

0_o

Sligocki: link collatz-like

2024-08-06T19:52:57Z

link collatz-like

← Older revision		Revision as of 19:52, 6 August 2024
Line 1:		Line 1:
	A '''consistent Collatz''' sequence is a sequence of integers which can be defined by a recurrence relation of the following form:		A '''consistent Collatz''' sequence is a [[Collatz-like]] 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>		<math>mx_{n+1} = rx_n + J[x_n\ \textrm{mod}\ m]</math>

Ais523: clarify the relationship to generalized Collatz functions

2024-08-05T22:59:34Z

clarify the relationship to generalized Collatz functions

← Older revision		Revision as of 22:59, 5 August 2024
Line 3:		Line 3:
	<math>mx_{n+1} = rx_n + J[x_n\ \textrm{mod}\ m]</math>		<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<!-- does negative r work too?-->, 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>.		where the sequence itself is <math>x_0, x_1, \ldots</math>, <math>m</math> and <math>r</math> are positive integers<!-- does negative r work too?-->, 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>.		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>.

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

2024-08-04T00:25:43Z

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

New page

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><br>
<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><br>
<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>)<br>
<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.

← Older revision		Revision as of 23:21, 7 October 2025
Line 1:		Line 1:
	A '''consistent Collatz''' sequence is a [[Collatz-like]] sequence of integers which can be defined by a recurrence relation of the following form:		A '''consistent Collatz''' sequence is a [[Collatz-like]] 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>		<math>mx_{n+1} = rx_n + J[x_n\ {\operatorname{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<!-- does negative r work too?-->, 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>).		where the sequence itself is <math>x_0, x_1, \ldots</math>, <math>m</math> and <math>r</math> are positive integers<!-- does negative r work too?-->, 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\ {\operatorname{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>.		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>.
Line 9:		Line 9:
	== Efficiently calculating consistent Collatz sequences ==		== 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:		For any given Collatz sequence, it is possible to calculate its sequence of remainders <math>x_n\ {\operatorname{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><br>		<math>w_n = x_n\ {\operatorname{mod}}\ m^{f(n)}</math>, except <math>w_0 = x_0</math><br>
	<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)		<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)

Line 24:		Line 24:
	The algorithm itself is:		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><br>		<math>j_n = m^{f(n)-1} J[w_{n-1}\ {\operatorname{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><br>
	<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>)<br>		<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>)<br>
	<math>w_n = w'_n \div m^{f(n)}</math> (which should always be an integer).		<math>w_n = w'_n \div m^{f(n)}</math> (which should always be an integer).