%26lt;0011 Em

For those new to the Collatz Conjecture

EDIT: Commented the latex tabular code. Get it here.

More after the break.

Upcoming: split the child propagation into its own thread, then create a second thread that reads from true queue top down to current, and writes to file.  It will eventually get IO bound, though, so perhaps I’ll just add a second queue and batch write calls on the popped elements once it’s closing on some memory limit.  Anyone have a better suggestion than XML for… really large columns of data?  Not that I’ll be able to touch the upper limit of $5.764 * 10^{18}$ (see here).  For giggles, if you will.

The program pops a value off the queue (in the initial case, 1) and tries to create both children- $2n$ and $\frac{n-1}{3}$, provided in the second case, that $(n-1) mod 3 = 0$.  As expected, the number of values grows somewhere under the order $2^n$ (if each number could be formed by both dividing by two and ALSO by multiplying by three and adding one, then there would be 2 points added per child per iteration- $2^n$).

The log2 view:

Test run halted after calculating 125,000,000 numbers.  Table formatting + pictures created with python utilities; I’ll pastebin the code eventually (EDIT: here).  Most of them are available in my stats blog (chapter 1, in this case).

Table!

$\begin{tabular}{ | c | c | c | c | } \hline Depth & Count & Depth & Count \\ \hline 0 & 1 & 28 & 18099 \\ \hline 1 & 2 & 29 & 24180 \\ \hline 2 & 3 & 30 & 32309 \\ \hline 3 & 5 & 31 & 43140 \\ \hline 4 & 8 & 32 & 57609 \\ \hline 5 & 13 & 33 & 76902 \\ \hline 6 & 19 & 34 & 102633 \\ \hline 7 & 30 & 35 & 137022 \\ \hline 8 & 41 & 36 & 182860 \\ \hline 9 & 57 & 37 & 244103 \\ \hline 10 & 83 & 38 & 325811 \\ \hline 11 & 114 & 39 & 434816 \\ \hline 12 & 155 & 40 & 580304 \\ \hline 13 & 216 & 41 & 774361 \\ \hline 14 & 293 & 42 & 1033079 \\ \hline 15 & 394 & 43 & 1378432 \\ \hline 16 & 536 & 44 & 1838945 \\ \hline 17 & 724 & 45 & 2453123 \\ \hline 18 & 971 & 46 & 3272729 \\ \hline 19 & 1307 & 47 & 4365597 \\ \hline 20 & 1753 & 48 & 5823419 \\ \hline 21 & 2354 & 49 & 7768300 \\ \hline 22 & 3156 & 50 & 10361932 \\ \hline 23 & 4225 & 51 & 13821917 \\ \hline 24 & 5668 & 52 & 18435615 \\ \hline 25 & 7586 & 53 & 24589116 \\ \hline 26 & 10136 & 54 & 26770255 \\ \hline 27 & 13542 & & \\ \hline \end{tabular}$