Collatz-inspired sequences

Nearly two years ago (3 posts ago, my post rate has really dropped…) I did a post titled “Alien Hailstone Numbers”, in which I explored different rulesets, expanding on a previous post (“The 2,3/7 rule and the Collatz Conjecture”) that looked at one such rule. This next part looks at what is not so much an extension of the standard Collatz rules, but rather something that exhibits similar behaviour to previous sequences explored. As before explained on those earlier posts, my interest is not so much attempting to prove anything (that would be far above my abilities), but rather the simple enjoyment of these chaotic sequences themselves.

I will be focusing on one particular rule I messed around with, so let me first explain how this even came about. The previous sequences were focused on the multiplier, trying to ‘balance’ out a certain set of dividing steps. I wanted to try doing some different operations to replace the dividing steps so I messed around with different rules to see if I got anything interesting. A vast majority aren’t particularly interesting as they often do one of three things: rapidly go to infinity, fall to 0, or settle at some value range that balances the operations being done to the numbers. One rule stood out as behaving similarly to the collatz sequences I have looked at previously, and this is the one I will be talking about.

Start with any positive integer. Multiply by 3, then find the binary complement to produce the next term – repeat until it reaches 0 or loops. The binary complement is an operation that when you convert your number into binary, you change the 1s to 0s and vice versa: 6 is 110 in binary and the complement of this is 001, which is 1. If you’re doing mental calculations a faster way is to simply take away the number from the next highest Mersenne number (one less than a power of 2), as they are repunits in binary (i.e 111…111). It’s an interesting operation and the results are highly volatile – the operation can result in a number thats 1 less than the starting number all the way down to 0. As for the multiplier, 3 is the same as the standard Collatz sequence, 5 seems to convincingly goes to infinity for almost all initial terms and 4 doesn’t produce interesting behaviour (as in binary it just adds two 0s on the end). As an example, starting with 2: multiply by 3 to get 6, convert to binary – 1102 and do binary complement – 0012 which is 1. Repeating with 1: multiply by 3 to get 3, convert to binary – 112, do binary complement – 002 which is 0. The sequence is thus [2,1,0]. Of course you can do all the multiplication in binary too, but this makes it easier to see what is happening.

The seed (initial value) of 3 gives the longer sequence [3, 6, 13, 24, 55, 90, 241, 300, 123, 142, 85, 0] – note that when it hit 85, triple this is 255, one less than a power of 2 and having the binary representation 111111112 which when inverted is 0. I haven’t tracked how often certain endpoints are reached, that might be another thing to explore another time (I constantly have to prevent my project extensions getting out of hand, or I’ll never finish anything!). It also has a surprisingly long sequence of 7 consecutively larger terms; I’m not sure how to determine if there is a limit to how long such sequences can go for. Sequences are chaotic and generally take longer to fall to 0 than does the standard Collatz rules. No loops exist up until at least 20,000. If you are familiar with my previous posts you’ll know that I have keen interest in seeing whether there are some sequences that take an inordinate amount of time to reach 0. I wouldn’t be writing this post if this weren’t true so its not exactly a revelation, but yes there are some surprisingly prolonged sequences I’ve come across.

The seed 12 takes 80 steps with a maximum of 328536 which is already comparable to the 111 step sequence from 27 with standard Collatz rules. The next record is from 28 whose length jumps by two orders of magnitude to 7572 steps and a maximum of the 54 digit integer 123130640068522377168864228132316865867184046004226894! The other notable one in this range is 50 which has a slightly shorter 5498 step and 4.94 * 1050 maximum. These are very much outliers, as a vast majority end quickly or join up to the longer sequences, which is similar behaviour to the standard and modified Collatz rules I’ve explored before. The next record holder is 227 which raises the bar by another two orders of magnitude: 664475 steps and a maximum of the enormous 3.26 * 10552, followed by 821 with 3180929 steps and 2.03 * 10933. At this point it seems like this is a rough maximum for how large these things get, with seeds like 1633, 6352 and 13340 being in the ~million step range. These took a not inconsiderable amount of time to compute with the code I had, roughly 20 minutes each. This indeed proved a sticking point, as I eventually reached a seed a couldn’t resolve with over 2 days of computation time. After attempting to break up the computation and asking other people with better computers to give it a try, asking in forums and even emailing Numberphile to no avail, I eventually threw in the towel and the enthusiasm to write up this post evaporated with it.

And there the project lay for over a year. A friend of mine was discussing some computer projects he was doing and I was reminded of this project, prompting him to offer to look at the code. A short time later he was back with code that was over 30 times faster than the old one! I wasted little time testing out the new code and the previous computing wall was broken in only about an hour and a half! The next record holder raises the bar by yet another two orders of magnitude: 22246 takes 120796789 steps (that’s over 120 million!) and a maximum of 9.38 * 108306. It’s clear that this algorithm supports some extremely long sequences, though as with the Collatz conjecture itself it is extremely likely that it is not provable that every seed eventually terminates. I haven’t explored higher as its better to end on a success than continue and end up with an even more intractable sequence to contend with, though I do remain very curious whether other fairly small seeds get stuck in the stratosphere, so to speak.

I feel as though every other post is an update for why I haven’t posted in ages so I’ll try to keep it brief. To be honest, it is mostly the usual suspects, but there is a project I’m working on – that if I’m able to meet the admittedly large ambition, I’ll be very pleased to announce it here. Not yet though! As for other projects, I have no idea. Fun fact – I was recently diagnosed with ASD (Autism Spectrum Disorder). Still digesting that one. Things could be on the up for me this year, guess we’ll have to wait and see. Until then, see you next post!

Advertisement

One thought on “Collatz-inspired sequences

  1. Pingback: Prove that f(x) = -1-3x (mod 2^p) is cyclic with period 2^p – Mathematics – Forum

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s