Assignment 1

The Collatz conjecture asks if, for any positive integer \(n\), the following procedure eventually halts:

• if \(n\) is \(1\), then HALT;
• if \(n\) is even, divide \(n\) by \(2\);
• if \(n\) is odd, multiple \(n\) by \(3\) and add \(1\).

Implementing this procedure has become a kind of FizzBuzz test when learning a new PL. To make it just a bit more interesting, implement the function verify_collatz which, given a number hi of type usize, verifies that the conjecture holds for every number up to and including hi. The function should not return anything, but you may want to include some print statements for your own benefit. Note that this function may not halt if the conjecture is false!

Determine a value of hi so that your implementation runs for a reasonable amount of time (let's say 5 minutes). How high can your implementation go?

Note: Make sure to run using cargo run --release to get full speed.

The Pólya conjecture, in rough terms, asks if, for any positive integer \(n\) greater than \(1\), at least half of all positive integers at most \(n\) have an odd number of prime factors (This has surprising connection to the Riemann hypothesis).

More formally, define \(\Omega : \mathbb N^+ \to \mathbb N\) so that \(\Omega(n)\) is the number of prime factors of \(n\) counting multiplicites. For example, \(\Omega(18) = 3\) since \(18 = 2 * 3 * 3\). Define \(\lambda : \mathbb N^+ \to \{-1, 1\}\) as

\begin{align*} \lambda(n) = (-1)^{\Omega(n)} \end{align*}

and \(L : \mathbb N^+ \to \mathbb Z\) as

\begin{align*} L(n) = \sum_{i = 1}^n \lambda(n) \end{align*}

Note that \(L(n) \leq 0\) if and only if at least half of all positive integers at most \(n\) have an odd number of prime factors.

The Pólya conjecture has been disproved, and the smallest counterexample is just shy of a billion: \(906,150,257\). When this number was found, it required some serious compute to verify. Our goal is to verify it on our laptops with a couple lines of code.

Implement the function verify_polya which, given a number hi of type usize, verifies the conjecture up to and including hi. The function should not return anything, but should stop if it finds a counterexample (and print it).

Find a value of hi so that your implementation runs for a reasonable amount of time (let's say 5 minutes). How high can your implementation go?

Note: Make sure to run using cargo run --release to get full speed.

(Optional) In the previous question you're not required to verify the minimal counterexample. The naïve solution likely won't be able to do this. The challenge: try to make your implementation in the previous problem as fast as possible. A couple things to try:

• Make sure you're cutting out any unnecessary computations of \(\Omega\).
• Compute prime numbers while computing \(\Omega\) and use those for later computations of the values of \(\Omega\) (you may want to look up Vec if you're interested in trying this).
• If you just want to verify the smallest counterexample, be careful about your choice of number types.
• Use a crate like slow_primes to help you with prime number calculations.
• Use a crate like bit_vec to store \(\lambda\) in a bit vector.

My implementation runs in about 100s on my laptop. Once you've optimized, have fun with other side-quests:

• Dealing with integer overflow (note that integer overflow is not checked at runtime in release mode).
• Determine how many counter examples there are below a billion.
• Determine the largest value of \(L\) below a billion.

(Double Optional) As in the previous problem, the naïve implementation of verify_collatz won't get you that far. But there are a lot of optimizations which can be done to make the code faster. In fact, a paper came out this year which gives improved verification algorithms for Collatz. The challenge: make your implementation of the first problem as fast as possible. If you want a target, take a look at this table and the definition of a path record. How high of a path record can you verify on your laptop? My not-terribly-optimized solution only gets me to about \(50\) in 5 minutes.