Scaling a Theoretically Proven Sieve for Collatz Verification

September 13, 2026

The Collatz conjecture is one of those mathematical problems that is easy to state and remarkably difficult to settle.

Starting with any positive integer, repeatedly apply the following rule:

The conjecture states that every positive integer eventually reaches 1.

A computational verification cannot prove the conjecture for all integers, but it can establish that the conjecture holds for increasingly large ranges. One approach is to use theoretically proven results to eliminate large classes of numbers before performing the more expensive verification.

This project uses that approach to construct a sieve for chronological verification of the Collatz conjecture. The theoretical basis for the sieve is described in the research paper Chronological Verification of the Collatz Conjecture using Theoretically Proven Sieves.

The original sieve generator was relatively simple Python code. It represented every sieve position as a Python boolean and built progressively larger sieves entirely in memory.

That worked well for small values of K.

It did not scale particularly well.

The Original Generator

The sieve is based on powers of two. A sieve with parameter K contains 2^K positions, with each position indicating whether that value can be skipped during verification.

The original generator began with a small, known set of positions:

current_sieve_pos = [1, 3, 5, 9, 13, 17, 19]

It then generated the next sieve by examining each position and either inheriting the result from the previous sieve or applying the proof procedure.

The representation was straightforward:

current_sieve = [False] * (2 ** K)

Unfortunately, a Python bool is not equivalent to a single bit of storage. A list containing millions or billions of Python objects has substantial memory overhead.

The output file was also stored in a different representation: one character per sieve position.

That meant a K=32 output contained 2^32 positions and was approximately 4 GiB in size.

The in-memory representation could require vastly more memory than the final output.

For example, generating the original sieve through K=30 consumed approximately 12 GiB of resident memory on my system.

The algorithm itself was not necessarily the problem.

The representation was.

Packing the Sieve Into Bits

The first major change was to replace the Python boolean list with a packed bitset.

Instead of storing one Python value for every position, eight sieve positions are stored in each byte.

A few small helper functions are enough to manipulate the representation:

def get_bit(sieve, index):
    return (sieve[index >> 3] >> (index & 7)) & 1


def set_bit(sieve, index):
    sieve[index >> 3] |= 1 << (index & 7)


def clear_bit(sieve, index):
    sieve[index >> 3] &= ~(1 << (index & 7))

This changes the storage requirement from roughly one Python list element per position to exactly one bit per position.

A packed sieve containing 2^K positions therefore requires:

2^K / 8 bytes

in memory.

This is a substantial improvement, but it does not completely solve the scalability problem.

A K=32 packed sieve still requires 512 MiB.

And the generator needs both the current and next sieve while constructing the next generation.

For larger values of K, even a packed in-memory representation eventually becomes inconvenient.

Streaming the Sieve

The next step was to stop requiring the entire sieve to exist in memory.

The new generator uses a streaming implementation once a configurable memory threshold is reached.

Instead of constructing the entire next sieve as a Python object, the generator reads the existing packed sieve from disk in chunks, processes those positions, and writes the resulting packed data to another file.

Conceptually, the process becomes:

current sieve on disk
        |
        v
    read chunk
        |
        v
  generate next chunk
        |
        v
 write chunk to disk

Only a relatively small portion of the sieve needs to be resident in memory at any one time.

The chunk size is configurable using --chunk-size.

The default is large enough to provide reasonable performance without making the working set unnecessarily large.

Two Generation Modes

There was no reason to make every sieve use the slower streaming path.

For smaller values of K, keeping the packed sieve in memory is both simple and fast.

The generator therefore uses two modes.

For smaller sieves, it continues to generate the next packed sieve entirely in memory.

For larger sieves, it switches to streaming generation:

K < memory threshold
    -> packed in-memory generation

K >= memory threshold
    -> streaming generation

The transition is controlled with:

--memory-threshold-k

This also means the user does not have to manually decide which implementation to use.

The generator can be run normally:

python generate-sieve.py --max-k 32

and it will select the appropriate implementation.

Parallel Streaming Generation

Streaming introduces another opportunity for optimization.

The next sieve is twice the size of the current sieve. It can be divided into two independent halves corresponding to the two possible offsets into the previous sieve.

The generator uses Python’s multiprocessing module to process these halves in parallel.

The number of worker processes can be configured with:

--workers

For example:

python generate-sieve.py --max-k 32 --workers 4

The workers operate on disjoint regions of the output file, allowing them to generate their portions independently.

This avoids requiring a large shared in-memory data structure just to parallelize the calculation.

Keeping the Existing Output Format

One deliberate choice was not to change the final bitset.txt format.

The internal representation is now packed, but the final output remains one character per sieve position.

That means existing users of the generated bitset do not need to change how they consume it.

The packed representation is an implementation detail used to make generation scalable.

At the end of generation, the packed representation is converted back into the original text format.

This also makes correctness testing particularly straightforward: the old and new generators can be compared directly.

Command-Line Configuration

The original generator required editing constants in the Python source.

The new implementation moves the important settings to command-line options.

For example:

python generate-sieve.py --max-k 30 --workers 4

The available options include:

--max-k
--chunk-size
--workers
--memory-threshold-k
--output
--verbose

The default behavior remains simple:

python generate-sieve.py

For users who want more control, the configuration is available without modifying the source code.

Verifying That the Optimization Did Not Change the Algorithm

Performance improvements are not particularly useful if they subtly change the mathematical result.

The most important test was therefore not a benchmark.

It was comparing the output of the original generator with the new implementation.

I retained the original generator and generated the same sieve with both implementations.

The resulting files were compared byte-for-byte and their SHA-256 hashes were calculated.

The new implementation was tested against the original from K=4 through K=32.

The outputs were identical at every tested value of K.

For example, at K=30, both implementations produced a 1.00 GiB output file with the same SHA-256 hash.

That gives considerably more confidence than simply checking that both programs finish successfully.

The new implementation is producing the same sieve, not merely a sieve of the same size.

Benchmarking the Difference

I also added a small benchmark utility to make resource usage easier to measure.

It uses psutil to monitor the generator while it runs and reports:

For example:

python benchmark-sieve.py --max-k 30

The benchmark runs the generator in a temporary directory and removes the temporary files when it finishes.

The benchmark tool itself is the only part of the project that requires the third-party psutil package. The sieve generator uses only Python’s standard library.

The Results

The difference becomes particularly noticeable at larger sieve sizes.

In one K=30 comparison, the original implementation took approximately 20 minutes and reached a peak resident memory usage of about 12 GiB.

The streaming implementation completed in approximately 4 minutes with peak resident memory of about 138 MiB.

The output from both implementations was exactly 1 GiB and had the same SHA-256 hash:

2d17c2e4ac82eb0c937fc10b2d3821daeaa75c1dd98d0f53c88d521d3a5043e7

In that test, the streaming implementation was approximately 79% faster while using approximately 99% less peak resident memory.

The improvement is not simply the result of throwing more RAM at the problem. The important change is that the generator no longer needs to represent the entire sieve using Python objects.

Estimating Sieve Size

There is an important distinction between the internal packed representation and the final output file.

The final bitset uses one character per sieve position, so its size is approximately:

2^K bytes

Each increase of K doubles the output size.

For example:

K=30  -> approximately 1 GiB
K=31  -> approximately 2 GiB
K=32  -> approximately 4 GiB
K=33  -> approximately 8 GiB

The streaming implementation makes larger values practical from a memory perspective, but it does not eliminate the storage or computational cost.

A sufficiently large sieve will still require substantial disk space and processing time.

What This Changes

The interesting part of this project is that the mathematical procedure did not need to be fundamentally redesigned.

The original implementation was easy to understand and worked well for small sieves. Its limitations only became apparent as the size increased.

At that point, the cost of Python’s object representation became much more significant than the underlying mathematical calculation.

Packing the data into bits, streaming it from disk, and parallelizing independent portions of the generation process turned out to be enough to make a substantial difference.

Most importantly, the optimization was validated against the original implementation rather than assuming that a faster implementation must be equivalent.

From K=4 through K=32, the generated bitsets are byte-for-byte identical.

The project still does not prove the Collatz conjecture. What it does is make one computational approach to its verification considerably more scalable.

Final Thoughts

This was a useful example of a performance problem where the algorithm was not necessarily the first thing that needed to change.

The original implementation was easy to understand and worked well for small sieves. Its limitations only became apparent as the size increased.

At that point, the cost of Python’s object representation became much more significant than the underlying mathematical calculation.

Packing the data into bits, streaming it from disk, and parallelizing independent portions of the generation process turned out to be enough to make a substantial difference.

Most importantly, the optimization was validated against the original implementation rather than assuming that a faster implementation must be equivalent.

From K=4 through K=32, the generated bitsets are byte-for-byte identical.

The project still does not prove the Collatz conjecture. What it does is make one computational approach to its verification considerably more scalable.

Categories: python , programming