### 3x+1, the update

Regarding the 3x+1 fun I've been having, I have some updates...

First, you will recall that I had taken a C program used to do massive computations on 3x+1, and optimized it by a factor of about 3x (no pun intended). I'm almost done implementing the C program in Smalltalk as well. This work involves the industrialization / productization of various bits of workspace code I used while doing the C version. With this Smalltalk code, I plan to verify a few ideas I have to make the C program run even faster.

Second, as mentioned in my earlier posts the T^(x) function is x/2 for even x, and (3x+1)/2 for odd x. Let's take a look at the below T^4(x) trace matrix. Each row corresponds to each x mod 16 value, and columns 2 through 5 correspond to T^1(x), T^2(x), T^3(x) and T^4(x).

- 16k + 0 8k + 0 4k + 0 2k + 0 1k + 0
- 16k + 1 24k + 2 12k + 1 18k + 2 9k + 1
- 16k + 2 8k + 1 12k + 2 6k + 1 9k + 2
- 16k + 3 24k + 5 36k + 8 18k + 4 9k + 2
- 16k + 4 8k + 2 4k + 1 6k + 2 3k + 1
- 16k + 5 24k + 8 12k + 4 6k + 2 3k + 1
- 16k + 6 8k + 3 12k + 5 18k + 8 9k + 4
- 16k + 7 24k + 11 36k + 17 54k + 26 27k + 13
- 16k + 8 8k + 4 4k + 2 2k + 1 3k + 2
- 16k + 9 24k + 14 12k + 7 18k + 11 27k + 17
- 16k + 10 8k + 5 12k + 8 6k + 4 3k + 2
- 16k + 11 24k + 17 36k + 26 18k + 13 27k + 20
- 16k + 12 8k + 6 4k + 3 6k + 5 9k + 8
- 16k + 13 24k + 20 12k + 10 6k + 5 9k + 8
- 16k + 14 8k + 7 12k + 11 18k + 17 27k + 26
- 16k + 15 24k + 23 36k + 35 54k + 53 81k + 80

- 16k + 0 0 0 0 0
- 16k + 1 1 0 1 0
- 16k + 2 0 1 0 1
- 16k + 3 1 1 0 0
- 16k + 4 0 0 1 0
- 16k + 5 1 0 0 0
- 16k + 6 0 1 1 0
- 16k + 7 1 1 1 0
- 16k + 8 0 0 0 1
- 16k + 9 1 0 1 1
- 16k + 10 0 1 0 0
- 16k + 11 1 1 0 1
- 16k + 12 0 0 1 1
- 16k + 13 1 0 0 1
- 16k + 14 0 1 1 1
- 16k + 15 1 1 1 1

But why does this happen in the first place? That is, why do parity matrices have all possible parity vectors? I have the following proof by induction to offer, which also explains the structure of the matrix. If you look at the trace matrix above, you will note that the even cases resolve immediately to the mod 8 matrix. But what about the odd cases? Those can be remapped to the mod 8 matrix too:

- 24k+2 => 8 * 3k + 2
- 24k+5 => 8 * 3k + 5
- 24k+8 => 8 * (3k+1) + 0
- 24k+11 => 8 * (3k+1) + 3
- 24k+14 => 8 * (3k+1) + 6
- 24k+17 => 8 * (3k+2) + 1
- 24k+20 => 8 * (3k+2) + 4
- 24k+23 => 8 * (3k+2) + 7

We can subtract 2 from both sides, and then since 3 is inversible we can multiply by 3^-1, leaving that r1 must be equal to r2 mod 2^m. This equivalence implies equality because 0 <= r < 2^m. Consequently, there are no duplicates, and so there are as many different rows as there can possibly be.

These observations about the even and odd cases show that each 2^m matrix is embedding the 2^(m-1) matrices twice: once for the even case, and once for the odd case. In the case of the even case, it prefixes the 2^(m-1) matrix with a leading zero in the parity vectors. The odd case prefixes the 2^(m-1) matrix with a leading one in the parity vectors.

The above proves the induction step. So what about the basis, i.e. the 2^1 matrix? Well, that's simply

- 2k+0 => 1k+0
- 2k+1 => 3k+2

- 2k+0 0
- 2k+1 1

Side comment: it's really fun to write Smalltalk code to run through the proof for a certain matrix, and then put that in an SUnit test.

Third, I began looking at join sieves in Smalltalk, too. From my earlier posts, remember that a join sieve is a T^k(x) matrix that is used to skip some cases that aren't interesting. All even cases are skipped in favor of the resulting odd cases. Also, since some T(x) paths join after a few iterations, e.g. T^3(8k+4) = T^3(8k+5) = 3k+2, we can skip processing 8k+5. Consider then a join sieve mod 2^m, storing whether each case should be analyzed in a large bit vector. In fact, the bit vector only records the information for odd cases, since obviously any even case would have a zero in the bit vector. This means that a 2^m sieve needs 2^(m-1) bits of storage. If m=20, the sieve requires 512 kilobits, or 64 kilobytes.

So, exactly how many byte values appear in the 2^20 sieve's bit vector? Exactly 32. First, we have 8 multiples of 8, from 0 to 56. Then, we have those same multiples + 128. And then, we have those 16 multiples of 8, plus 1. In other words,

## No comments:

Post a Comment