collatz_dict, a Python code which demonstrates how the Python dict variable type can be used to efficiently record data about the Collatz iteration.
The rules for generation of the Collatz sequence are recursive. If T is the current entry of the sequence, (T is assumed to be a positive integer), then the next entry, U is determined as follows:
Each integer N has a Collatz successor C(N). If we start with an arbitrary starting value N, we may wish to record the sequence of pairs (N,C(N)) that we generate. Now if we choose a new starting value, it may happen that at some point, we reach a value already contained in our records. Then we can stop the iteration immediately, since we already have computed the remaining information.
One way to do this might be to imagine a vector CVAL of length N_MAX, initially zero. If we start with some value N, and compute C(N), then we set CVAL(N) = C(N). Our next step is to compute C(C(N)), and we can set CVAL(C(N)) to C(C(N)) and so on, until we reach a value of 1, or until we encounter a case in which the corresponding entry of CVAL has already been calculated.
A vector approach like this has some disadvantages. If we impose a maximum value for our vector, then we must typically allocate a lot of space, since the Collatz sequence occasionally gets quite large. And really, we waste most of this space, since the Collatz sequence jumps around, leaving great gaps. Even if we run 100 tests, we are unlikely to fill much of our vector.
If, on the other hand, we are allowed to create a vector that can grow, but still must allocate one entry for every index up to the current maximum, then we encounter the overhead of recopying the vector into a larger version whenever our sequence exceeds the current size.
From a user's point of view, the Python dict variable can be a very efficient way of exploring the Collatz sequence. We start with an empty dict. Each Collatz experiment begins with a value N and its successor C(N). We add N as a key, and C(N) as its value. We continue iterating in this way. The dict will let us know if the latest value of C(N) should not be used to generate a new key, because that key is already in the dict. We leave it to Python to efficiently manage the storage and update of the dict.
The computer code and data files described and made available on this web page are distributed under the MIT license
collatz_dict is available in a Python version.
collatz_recursive, a Python code which demonstrates recursive programming for the simple Collatz 3n+1 problem.
polpak, a Python code which evaluates a variety of mathematical functions, polynomials, and sequences, including Bell, Benford, Bernoulli, Bernstein, Cardan, Catalan, Charlier, Chebyshev, Collatz, Delannoy, Euler, Fibonacci, Gegenbauer, Gudermannian, Hermite, Hofstadter, Jacobi, Krawtchouk,' Laguerre, Legendre, Lerch, Meixner, Mertens, Moebius, Motzkin, Phi, Sigma, Stirling, Tau, Tribonacci, Zernike.