32:T12b4,md`Now, the immediate reaction to the Collatz conjecture is that some number, with some arbitrarily large number of digits, must approach infinity instead of collapse to 1, because multiplying by 3 grows the number in question more than dividing it by 2 does. Common sense follows, as long as there is some number that can escape the bounds of the number sets mathematicians have called "stability orbits", then that number must fly off into the deep numeric spaces of infinity. Like that probe that recently passed Neptune… or Io, or something. One might theorize that such a number would have to be both arbitrarily large, and prime. Prime numbers are always doing kooky shit. But no number ever does break out of the collapse bounds, and no number ever can. This is because of a few simple truths about integers: - An even integer multiplied by an even integer will result in an even number - An even integer multiplied by an odd integer will result in an even integer - By the commutative property, this holds true in the converse case of odd times even - An odd integer multiplied by an odd integer will result in an odd integer These properties lay the foundation of why every number eventually reduces to 1 with the Collatz algorithm. Unsure of how? Maybe this property will make it clearer: - Adding 1 to any integer result in the new integer being odd if the prior integer was even, or even if the prior integer was odd With those rules established, we're on the path to proving inevitable Collatz collapse. The reason why has to do with the steps this algorithm takes. See, whenever we multiply an odd number result by 3 and then increment it, our new number is _always_ going to be even. odd times odd is odd, odd plus 1 is even. Therefore, _the immediate step after we triple and increment any odd number will invariably be ${tex`\frac{n}{2}`}._ But that's old hat. That's not the bee's knees. That's been common knowledge among Collatz collaboratorz for a while now. It's so uninteresting that the function for an odd number is sometimes shorthanded to ${tex`\frac{3n + 1}{2}`}. If I want to make rent this year, I need to tell you something new, something novel, something Nobel Prize-worthy. ## NO PRESSURE RIGHT?? So let's take a closer look at the step _after_ that divide-by-2, shall we? What happens there? Well, if the result of halving our last number was odd, you rinse and repeat; multiply by 3 and add 1 again. Badda bing, badda boom. But if it's even? You halve it _again_, suddenly giving you ${tex`\frac{3n + 1}{4}`}, a number that's a bit smaller than what you'd had two steps prior. Maybe you have an odd number again now, and you get to multiply and increment another time, but if you halved what you had after halving it just before, and the result is **still** even, you have to halve it yet again. And you keep on halving what you have until you've halved so many halves that you finally have a number you can halve no more. It... it's odd. Your number is odd again. ###### ...I got an English degree, I like wordplay, okay? --- **That** is a Collatz reduction trap; a sequence in the algorithm where divide your result by two, for at least two consecutive steps, before the result is odd, and your next step is ${tex`3n + 1`}. Depending on the number of steps the algorithm spends in the trap, the resulting ${tex`n`} can be anywhere between ${tex`\frac{3}{4}`} the result of your most recent multiply step, to a number exponentially smaller than that. The reason \`collapz(53)\` reaches ${tex`1`} a full hundred steps sooner than \`collapz(27)\` is because \`collapz(53)\` enters a reduction trap as soon as its second step, and then after being tripled and incremented again (the second time it does so), it immediately enters its terminal trap (the trap which ultimately reduces it to 1). If you're following along with the way these steps unfold, you might've have noticed this pattern in the algorithm: - #### The step immediately following ${tex`3n + 1`} will _always_ be ${tex`\frac{n}{2}`} - #### The step immediately following ${tex`\frac{n}{2}`} _can possibly_ be ${tex`3n + 1`} Which means that, *at best,* ${tex`3n + 1`} __may__ be applied once for every _other_ step, but ${tex`\frac{n}{2}`} can end up being applied consecutively any number of times after it's invoked once. For all the statistics lovers out there, that ultimately means ### When applying the Collatz algorithm to any given number, ${tex`3n + 1`} will be applied in _at most_ 50% of the steps, whereas ${tex`\frac{n}{2}`} will be applied in _at least_ 50% of the steps. In fact, we can definitely prove that's the case for every number already proven to collapse to 1. Let's make an update to \`collapz(n)\` that keeps a tally of each kind of step. `33:T68a,{ const binstring = '100110101110'; const converted = +`0b${binstring}`; return md`...What you'll see is almost akin, in my opinion, to a one-dimensional variant of Conway's Game of Life. Here is where we can see why every number eventually collapses to 1. So, why are we looking at these binary sequences? Every \`0\` in our binary sequence represents a power of two that we can divide *by* two to remove. The number ${converted}, for instance, is \`${binstring}\` in binary. Each of those \`1\`s being a power of two means we can also express ${converted} as ${tex`2048+256+128+32+8+4+2`}, which is definitely a bit more verbose, but it is also more instructive. If we were to not have the final three powers of two, we would then have ${0b100110100000}, or \`100110100000\`, or
${tex`2048+256+128+32`}, whichever way you want to visualize it. We can divide this number by two **as long as our smallest expressed power of two isn't equal to \`1\`.** If it is equal to 1, then we know we have an odd number and that we will subsequently triple and increment our number. The binary format also illustrates how tripling a number is essentially the same thing as adding the double of it to itself. By adding \`10\` to any place where a digit is \`1\` (literally, adding, so \`1 + 10 = 11\`, not \`10 + 1 = 101\`). So tripling ${html`

`} means it becomes \`100001011\` Notice that we "carry the one" in the case of the 16-digit, which results in a cascading change of all of the larger digits from 1 to 0 until the 256-digit changed from 0 to 1. Incrementing by 1 now would result in us having \`100001100\`, or \`268\`.` }34:T69c,md`It can be said that whether the next step in the algorithm for any given number is ${tex`\frac{n}{2}`} or ${tex`3n + 1`} is determined solely by whether the final digit of its binary form is \`0\` or \`1\`. Any time our number ends with \`0\`, it's divisible by 2. Any time it ends with a sequence of \`0\`s, it's in a reduction trap. And, as we already know from the rules we've established earlier, any time we triple and increment our number, its binary form will change from ending with a 1 to ending with at least one 0. Another thing to take note of is how the counts of the bits changed in the example up above. Before we do anything, we have three \`0\`s and four \`1\`s. We would expect to see more \`1\`s after tripling it. After all, we just applied a step that turns every \`1\` into \`11\`, that's double the \`1\`s! Except that in cases where there's already a \`1\` in the place where our new one would go; since we have to carry the one, we flip that bit back to a \`0\`, and then carry the one another digit up through the positions. It turns out, the more bits we have that are already \`1\`s, the more potential tripling a number has to create large sequences of \`0\`s. We already know the step of incrementing our number by 1 creates at least one \`0\` bit, and possibly a sequence of \`0\`s, at the end of our number's binary form, but it also had another side effect: We had four \`1\`s after multiplying by 3 – the same amount we had before multiplying – but after incrementing by one, our binary form now has only _three_ \`1\`s. About how many more steps do you think our original number, ${0b1011001}, has before it collapses to 1? Why don't we find out? `35:T1823,md`We're just about ready to crack this case, I'd say. By sorting these numbers from longest to shortest Collatz collapse paths, we begin to see why certain numbers take so much longer to terminate than others. How large the number is initially plays a small part in it, but the bigger determining factor is _the distribution of active (\`1\`) bits within the number's binary (Base Two) form._ When you think about it, this makes sense. Tripling a number flips its bits in a manner not unlike the way laying down a disc in the board game Reversi (or Othello) flips the tiles in between the two pieces at the ends of a row. The comparison to Conway's Game of Life is more illuminating. In that simulation, a certain number of active bits, adjacent to one another, will create a number of new bits along one of their common edges. More bits than that adjacent to each other, though, consume and zero themselves out, leaving an empty space on the board where "life" once was. In the same way, our numbers thrive when their active bits have space enough to germinate a bit, before the empty, terminal space – representing the fact that our number is even – is inevitably created from incrementing our odd number by 1, and then swept clear by being halved as many times as is necessary for the resulting number to once again become odd. So, let's do a thought experiment: Supposing we were to fashion a binary sequence of arbitrary length ${tex`B`} with its active bits distributed in such a way that the number the sequence represents underwent as many steps of the Collatz algorithm as any number derived from a binary sequence ${tex`B`} bits long possibly could. _Will this number's binary form begin to develop pockets of \`0\` bits interspersed between its \`1\` bits as a matter of course from being tripled?_ Yes. Setting aside the fact that the number's binary form will necessarily begin with some amount of \`0\` bits to accomodate the effects tripling the number has on its \`1\` bits, as the number is tripled additional times throughout the algorithm, the clusters of \`1\` bits will have less and less space between them, until such a point that the proximity will lead to instances where tripling the number results in summing the bits and carrying the one, flipping clusters of \`1\` bits into sequences of \`0\` bits, flanked on either side by singular (or, at best, a few) \`1\` bits, the left bit being the carried-one from the summing, and the right bit being the persisted odd bit from the tripling procedure. Except in the case, of course, where that \`1\` bit is the rightmost digit to the number, in which case, it flips to a 0 after being incremented. _Will there ever be a time at which the incrementation invoked by ${tex`3n + 1`} does not result in an even number?_ No. The rule of multiplication at the start of this proof — that multiplying an odd integer by an odd integer results in an odd integer — always holds true, no matter how large our integer is. We can observe this rule by looking at the integer's binary form, and seeing that the rightmost digit remains a \`1\` after tripling, and then becomes \`0\` upon incrementing. _Will there ever be a phase of our algorithm where a large enough number will be tripled and incremented more than once in a row?_ No. After tripling and incrementing our number, the result will always be even, and we will therefore always have at least one step where we halve our number in between steps where we triple and increment it. _Do we necessarily have instances during the algorithm where we will halve our number multiple times consecutively?_ Yes. As our number is tripled and incremented, we necessarily arrive at instances when our number, which can be expressed as multiple powers of 2, becomes a new number which can be expressed as larger (but fewer) powers of 2. A side effect of being expressed with fewer, larger powers of 2 is that our number is eminently more ready to be divided by 2 cleanly, and thus remain an even number after a greater amount of consecutive instances of being divided by 2. _Will larger numbers undergo more steps of the Collatz algorithm than smaller numbers?_ Not necessarily. As the sample set of all numbers between 1 and 1023 demonstrates up above, the number of Collatz algorithm steps a given number will undergo is not tied directly to how big of a number it is. 27 undergoes 111 Collatz algorithm steps before collapsing to 1. 1023 undergoes 62 steps. A number literally 1% the size of the other collapses to 1 in nearly double the amount of steps. That being said, the size of a given number is not completely ineffective at predicting whether it will go through more or fewer Collatz steps than another number. A larger number is more likely to be the sum of a set of powers of two that is more conducive to persisting through a greater number of Collatz algorithm steps before collapsing to 1 by way of reduction traps. _But can you prove that there **isn't** a positive integer which will break the pattern and expand toward infinity?_ I feel like I just did, but if that didn't satisfy you, dear mathematician, I find it ironic that when I tell people they can't prove my pants **weren't** stolen by a pink, time traveling unicorn, I'm told that I'm "scaring families" and that I "need to leave this Arby's before the police get involved", whilst YOU... **But,** if you really feel like trying to prove me wrong, just below this is \`bigCollapz\`, its binary-tracking cohort, \`bigBinCollapz\`, and even a little slider and sample run of the Collatz algorithm on a number that's just a hell of a lot of \`9\`s just waiting for you to try to make me eat my hat (the unicorn, sadly, ate my pants before you could get here). And by "hell of a lot", I mean that it is ${tex`9 * (10^{${numberOfNines}}) + 9 * (10^{${numberOfNines-1}}) + 9 * (10^{${numberOfNines-2}}) ... + 9 * (10^{0})`}, so... pretty sure I've covered all my bases. _Will every positive integer, when given as input to the Collatz algorithm, eventually collapse to 1?_ In a definitive word (submitted for the approval [and cash awards] of all concerned interests): Yes. `36:[] 30:{"title":"So, this whole \"Collatz Conjecture\" thing...","cells":[{"id":0,"value":"md`# So, this whole \"Collatz Conjecture\" thing...`","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"md`I'm honestly a little flabbergasted at some of the things mathematicians have deemed \"hard\" problems. I mean, Navier-Stokes, sure. Birch & Swinnerton-Dyer, alright. But, inasmuch as I struggle to perform the Herculean task of counting up money (which, I must assure you, is much more difficult when you have dyscalculia), I can only scratch my head and giggle, panickingly, when I ask the question,\n\n${html`\"Seriously, nobody's proven the Collatz Conjecture yet?\"`}\n\nBut, Donald Trump was president, coronavirus continues to ravage the planet, people think _Shrek_ was funny, and this is the world we live in. \n\nNo, nobody's proven the Collatz Conjecture yet.\n\nSo let this Bachelor (Arts, not Sciences) of English who stans Digimon way too hard do it, I guess.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"md`## SURE, SHOULD BE FUN`","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"md`The first thing we should define, if we want to be \"\"\"official\"\"\" here, is the conjecture itself.\n\nIt goes a little something like this:\n\n> ##### Given a positive integer ${tex`n`}, if we continually take ${tex`\\frac{n}{2}`} when ${tex`n`} is even, and ${tex`3n+1`} when ${tex`n`} is odd, does every possible input ${tex`n`} eventually reduce to ${tex`1`}?\n\nIn a definitive word (submitted for the approval [and cash awards] of all concerned interests): Yes.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":166,"value":"md`Here's a simple implementation of the Collatz Conjecture's algorithm. In addition to determining if the number reduces down to 1, it reports the number of transformations it took to do so.\n\nGiven what it measures, and that the problem itself is the Collatz Conjecture, I've found it fitting to name this function _\"collapz(n)\"_\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":56,"value":"function collapz(number) {\n if (number === 1) return 0\n if (number > 0 && Number.isInteger(number)) {\n const updated = (number % 2 === 0 ? (number / 2) : (3 * number + 1))\n return 1 + collapz(updated)\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":331,"value":"md`If we give \\`collapz(1)\\`, then the number of steps we took to get there is returned, which is 0 in the direct-call case. Then (assuming you didn't try to be clever and give a negative integer, a decimal value, or anything that isn't actually a number), \\`collapz\\` recurses until either the \\`number\\` it is processing becomes 1, or your call recurses one too many times in trying to please you, and your Javascript environment judges your call to be killed with brutal swiftness, and expediently cleared from memory (how _could_ you, reader?). If you do murder your \\`collapz\\` call, then be happy to know that there's an iterative form of this function, \\`bigCollapz(n)\\`, which is both much less bloodthirsty, **and** capable of working on arbitrary-precision integers. I'll be circling back to it much, much later.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":58,"value":"collapz(5)","pinned":true,"hidden":false,"mode":"ojs"},{"id":175,"value":"md`That... was a bit of serendipitous reflectivity on my part. But let's prove it doesn't just return the number you give it...`","pinned":false,"hidden":false,"mode":"ojs"},{"id":169,"value":"collapz(7)","pinned":true,"hidden":false,"mode":"ojs"},{"id":349,"value":"md`Yes. There we go!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"collapz(11)","pinned":true,"hidden":false,"mode":"ojs"},{"id":171,"value":"collapz(27)","pinned":true,"hidden":false,"mode":"ojs"},{"id":269,"value":"collapz(53)","pinned":true,"hidden":false,"mode":"ojs"},{"id":177,"value":"md`I know you're probably thinking \"Woah, how does it take 27 over 100 steps to collapse down to 1, when a number just under twice as big as it takes barely more than 10 steps?\"\n\nThe answer to that question, my friend, is because of a set of numbers I'm going to call _Collatz reduction traps_.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":183,"value":"tex`64 \\Rightarrow 32 \\Rightarrow 16 \\Rightarrow 8 \\Rightarrow 4 \\Rightarrow 2 \\Rightarrow 1`","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":492,"value":"collapzStepTally = (number) => {\n const steps = {tripled: 0, halved: 0}\n let updated = number;\n while (updated !== 1) {\n if (updated % 2 === 0) {\n updated /= 2\n steps.halved += 1\n } else {\n updated = 3 * updated + 1\n steps.tripled += 1\n }\n }\n return [steps.halved + steps.tripled, steps]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":502,"value":"md`Our new tallying function runs through the same Collatz process, counting up the number of times the number is halved vs. the number of times it's multiplied (and incremented), and returns the sum of those two numbers as the total number of steps it's taken, alongside the counts, split apart (we didn't go through the trouble of tallying them for our health, after all). Now what would make a good sample of numbers to go through? Hmm… how about, 1 through 1023? I would stop at 1000, but that brings us so close to the end of the 10-bit limit, so why not round it out?`","pinned":false,"hidden":false,"mode":"ojs"},{"id":506,"value":"tenBitTallies = Object.fromEntries([...Array(1023)].map((_, dex) => [dex+1, collapzStepTally(dex+1)]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":583,"value":"md`You know what? That's too much data. I've decided. Let's just focus on 1 through 255 for right now.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":584,"value":"Object.fromEntries(\n Object\n .entries(tenBitTallies)\n .slice(0, 255)\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":490,"value":"md`As expected, every number from the sample is halved more than 50% of the time and multiplied and incremented less than 50% of the time. In fact, it looks like nearly all of them hold steady with a multiplication rate of just a bit more than 1/3 of the steps, and a halving rate of just under 2/3 of them. There are a couple of outliers there, though, such as 87, which gets multiplied only 9 times out of 30 steps and halved 21 times. I wonder why that is... :thinkingface:\n\nMYSTERY! But I'm sure it'll be explained in the next phase of this proof ;)\n\nNow that we've established that, let's look at why ${tex`3n + 1`} will never approach being applied for 50% of the steps of the Collatz algorithm, for any number, ever*.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"md`This next part would be easier to visualize if I had some way of representing numbers more suitably for our needs… which is why it's so great that I do! Your device is already capable of utilizing this format of representation; in fact, it's how every computer ultimately represents **all** data. It's binary! (yaaay!)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":310,"value":"tex`27 \\Rightarrow 0b${(27).toString(2)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":304,"value":"md`Binary (or, for the mathematicians in the crowd, \"Base 2\") is the perfect way to represent our numbers for this problem. Every positive, whole number, can be expressed in binary terms, and expressing numbers this way gives us a very clear understanding of how they change when we triple and increment them, and an **especially** clear understanding of how they change when we divide them by 2.\n\nHere's a modified form of our \\`collapz\\` function that will keep track of each number we go through along our input number's path to 1, as well as the binary representation of each of those numbers.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"collapzWithBinaries = (number) => {\n let steps = 0,\n updated = number,\n bins = [[number, number.toString(2)]],\n longest = bins[0][1].length;\n while (updated !== 1) {\n updated = updated % 2 === 0 ? updated / 2 : 3 * updated + 1;\n let bin = updated.toString(2);\n longest = Math.max(longest, bin.length);\n bins.push([updated, bin]);\n steps++;\n }\n return [steps, bins.map(([num, bin]) => [num, bin.padStart(longest)])]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":477,"value":"md`To make the binary sequences easier to compare, the beginning of each one is padded with a number of spaces equal to the difference between the length of the longest binary sequence and its own length.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":325,"value":"collapz27result = collapzWithBinaries(27)","pinned":true,"hidden":false,"mode":"ojs"},{"id":212,"value":"collapzWithBinaries(53)","pinned":true,"hidden":false,"mode":"ojs"},{"id":324,"value":"md`Using our \\`collapzWithBinaries\\` function, we can note an interesting trait about our two flagrantly disproportionate Collatz numbers from earlier, 27 and 53. It turns out that \\`27\\` literally passes _through_ \\`53\\` at its 100th step. But I digress; what I wanted to draw attention to here is the binary sequences for each of the numbers at each step of the algorithm. If you go ahead and expand the following array result...`","pinned":false,"hidden":false,"mode":"ojs"},{"id":367,"value":"collapz27binaries = collapz27result[1].map(([num, bin]) => [num.toString().padEnd(4), bin])","pinned":false,"hidden":false,"mode":"ojs"},{"id":696,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":372,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":529,"value":"collapzWithBinaries(89)","pinned":true,"hidden":false,"mode":"ojs"},{"id":532,"value":"md`Wow. Well done, 89! You had a bit more life left in you than _I_ thought, at least. But, I mean, you certainly don't come anywhere close to 27's record. Talk about a powerhouse! Five initial bits, and 27 goes through more steps before collapsing to 1 than over 80% of the first 1023 positive integers.\n\nHey, supposing we organized that dataset according to how many steps each number took to collapse to 1 and then took a look at their binary representations, do you think we'd find any interesting correlations?\n\nDo you think I'd ask if the answer was \"no\"? ;)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":573,"value":"descTenBitTallies = Object.entries(tenBitTallies)\n .sort(([_A, [totalA]], [_B, [totalB]]) => totalB - totalA)\n .map(([number, [totalSteps, {tripled, halved}]]) => [+number, (+number).toString(2).padStart(10), totalSteps, tripled, halved])","pinned":false,"hidden":false,"mode":"ojs"},{"id":613,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":515,"value":"md`###### *Yes, ever. And if you'd like to claim otherwise, go ahead and find one. I'll wait.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":98,"value":"function bigCollapz(bignumber){\n let steps = 0;\n let updated = BigInt(bignumber); // just in case a regular-sized int is provided\n while (updated !== 1n) {\n updated = (updated % 2n === 0n ? (updated / 2n) : (3n * updated + 1n));\n steps++;\n }\n return steps\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":225,"value":"function bigBinCollapz(bignumber){\n let steps = 0;\n let updated = bignumber;\n let bins = [bignumber.toString(2)];\n let longest = bins[0].length;\n while (updated !== 1n) {\n updated = updated % 2n === 0n ? (updated / 2n) : (3n * updated + 1n);\n let bin = updated.toString(2);\n longest = Math.max(longest, bin.length);\n bins.push(bin);\n steps++;\n }\n // bins = bins.map(bin => bin.padStart(longest, \" \"))\n return [steps, bins]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":130,"value":"viewof numberOfNines = slider({min: 1, max: 7500, value: 2000, step: 1})","pinned":true,"hidden":false,"mode":"ojs"},{"id":83,"value":"toTheNines = BigInt(\"9\".repeat(numberOfNines))","pinned":true,"hidden":false,"mode":"ojs"},{"id":112,"value":"bigBinCollapz(toTheNines)","pinned":true,"hidden":false,"mode":"ojs"},{"id":191,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W36","stdlib":"1","titling":"auto"}