If some giant start number m>1 were to loop, could m+1 also loop?
I’ve been looking at this exact type of thing for a while now, and I’ve found a lot. The reason this all matters is at the bottom of my message.
If m was contained in a different loop than m, it would almost certainly be impossible, so I’m guessing you’re asking if m and m+1 will become the same loop, where it would loop back to either m or m+1, but not both.
I know that when two consecutive numbers join into the same path, there are two ways it will occur, first, when they reach the same number after the same number of steps, or they reach a similar number after different amounts of steps. The first is more regular and predictable, because you can go from one that works to infinitely more, like this: m, m+1 both become w after k even steps and j odd steps means that (2^(k+1))n+m and (2^(k+1))n+m+1 both become 2n*(3^j)+w. w doesn’t have to be the first number in common, but it makes it easier. I call these merge families.
To show a loop exists, you just need to find an endpoint of a merge lands within one of m, m+1, … m+r-1, or show the endpoint of that merge will eventually become one of those values.
With a smallest type of merge in a merge family, like 4,5,6 merging at 4 after 6 steps or 28,29,30 at 40 after 10 steps, because 3^j is usually larger than 2^k, (after removing a factor of 2) the endpoint of a merge will go from less than the run of consecutive numbers to greater than the run of consecutive numbers. If one of these endpoints lands within one of these ranges, then a loop could exist. If proven that the endpoint must land strictly less than and greater than the run of consecutive numbers that merge, then m and m+1 wouldn’t be able to get to the same number after the same number of steps.
I’ve proven that arbitrarily long merges exist, which I will share, because it ups the chances of the endpoint of the merge to land in the run m, m+1, … ,m+r-1. In other words, the run r can be arbitrarily big. So by splitting the number line into 3 sets where each is from numbers that take 1, 2, and 0 mod 3 steps to reach 1, consecutive numbers in the same set will be at the same number one after the same number of steps, which always happens to also have the same number of even and odd steps for each of the consecutive numbers. This means that using the merge family formula with the first occurrence of the consecutive numbers in the set all becoming the same, a merge of the length of the consecutive string can be constructed. Now, if a subset of the natural numbers has positive lower density, then it contains arbitrarily long runs of consecutive integers iff the set is not eventually periodic with small period or bounded gaps. Now suppose a period p exists, meaning eventually all x in the set will also have x+p in the set. p would have to divide the differences of all the arithmetic progressions contained in the set because membership repeats every p, so p|2^(k+1) for infinitely many k, implying p is 1 and that set has every number, but we don’t see that because there are 3 sets, about 1/3 density, which is a contradiction so there is no period and there are arbitrarily long runs. I’ve also proven this the other way by showing it doesn’t have bounded gaps which implies the other sets have unbounded runs.
It’s not too hard to see that as runs grow large, the time it takes to merge also gets large. I’ll show now a proof that there are infinitely many merges of length 3 that have times of any number excluding 1-5 and 7. For any run of length r, only finitely many step patterns can produce merges of run size less than or equal to r, and each occurs at only one step count, so small merges can only happen finitely many merge times. Once they have passed, the max run size stays above r for all later step counts. The point where the max run size stays above 3 is from 8 on.
Step patterns mean the different configurations of even and odd steps like how 4,5,6 and 28,29,30 have different steps even though they are both runs of 3. The max run size means the maximum r that exists for any one merge time like the maximum run size for a merge time of 10 is 5, because of the merge with 98-102.
Some examples of merges I have found are given like this: amount in run, and lowest number in run. Remember any merge is part of an infinite merge family, so one means infinitely many of that type will appear. (3,4),(3,28),(3,44),(3,49),(3,193),(3,209),(3,401),(3,177),(3,188),(4,103),(4,314),(4,5066),(4,5100),(4,5196),(4,5163),(4,5364),(4,5372),(4,5412),(4,5596),(4,5740),(4,6267),(4,6876),(4,4972),(4,7659),(4,7836),(5,98),(5,4971),(5,5590), (5,628),(5,290),(5,130),(6,386),(6,8394),(6,5848),(6,840),(7,943),(7,4937),(7,8065,(8,1494),(8,8385),(9,1680),(10,6288),(13,5313),(14,2987),(17,7083),(25,57346),(27,252548),(29,331778),(30,524289), (40,596310),(41,2886352),(47,3247146),(52,3264428),(60,5158596),(65,5772712),(77,13019668),(89,18341744),(96,24455681),(98,98041684),(120,136696632),(127,271114753),(130,361486064),(136,406672385),(152,481981441),(174,711611184),(176,722067240),(201,1202088120),(207,1352349136),(235,2095144704),(242,2832649952),(235,3298601216),(266,4190530500),(284,4248975008)
They run size grows slowly, as you can see.
I have another page-long proof that all odds apart from 1 will reach a number x that merges with a consecutive number x±1 ,proved case by case by going odd mod 6. This is what I proved after I had an incorrect proof that no loops can have m and m+1 merge into the loop. If someone reproved the part I had incorrect, which is what this start numbers m and m+1 into loop thread is about, then no loops could exist.
1 Like
@HungryMonkey7 super nice study of how the paths of numbers coalesce. Looks like if m reaches n (without passing through m+1), and m+1 also reaches n (without passing through m), then m and m+1 aren’t in the same loop.
There’s also a question of whether m and m+1 could be in different loops. For 5n+1, 26 and 27 participate in different loops, so probably there’s no reason it can’t happen.
I haven’t found much more as in proofs for consecutive numbers being related through loops as of late, but I have at least two good ways that seem to work to find merges. One is to take for some integer d, all the numbers 2^d+1 through 2^d+2^d and follow each of their paths to find which ones merge and which ones don’t for 2d-1 number of steps. What I do is I list them all vertically as say, 64n+1, then 64n+2… to 64n+64 and then each Collatz step is one column to the right.
The other method I know apart from brute force is to look at the 3 unique sets of numbers where in each set are all the numbers that reach 1 in 0 steps, 1 step, or 2 steps mod 3. Then by picking numbers from the same set and using the following to get the family, (with the earliest point x and y are both 4=m), you get the merges. If x and y each merge to m after k even steps and j odd steps, then (2^(k+1))*n +x and (2^(k+1))*n +y in the same manner will merge to (3^j)(2n)+m.
I’ve proved that 8n+4,8n+5 both becoming 6n+4 is the only merge with one odd, and it is the smallest merge, and I’ve found it pops up at the end of EOEO paths if you line them vertically and shift them so that the top row just contains a number two less than one or a prime and just below that is one more than it, and left of that is twice the larger one, and below the left one is one more than it, then one left of that is twice that, and so on, down and left, +1 and x2. The merges occur when Collatz is followed to the right, one to two steps after they stop being one apart.
I’ve also proven that no merges have 0 odds, none have one more odd than even, and none have an equal number of evens to odds. Since m is the first moment both paths are the same, it must be even and 6n+4 to be an input to even and odd.
I don’t have a proof, but I think it is possible that if two different numbers merge such as an+t and an+s then they must have some point in their future or past where they are exactly one apart, like bn+r and bn+r+1.
I have found that infinitely many consecutive merges exist for ALL 6n+4, and that if ANY two numbers merge (In the same number of steps) there are definitely numbers x and x+1 that occur either before or after the step containing the chosen numbers that merge, that form a consecutive merge.
What I did to find this out was by taking inspiration from a popular visual for the Collatz conjecture with one, two, and four in the middle in a line and at 16 it branches in a circular direction and so on (it’s not that important). So I had 6n+4 in the middle and I took two paths from it: one with 2n+1 and 12n+8. From 12n+8 I went to 24n+16 and from that one I branched into 8n+5 and 48n+32. I just kept doing this and whenever I reached an even (apart from (12n+8)*4^k because it can’t be 4 mod 6) I would find for which number mod 3 n would have to be to be 4 mod 6, and I would have one path being a normal path and at the end 2(an+b), and along the other path I would have n=3m+0,1,or2, and at its end it has what it would be for (x-1)/3, but with m. For example, from 2n+1 next is 4n+2 and that goes to 8n+4 and the other path is n=3m+2 leading to 4m+3. From this I could keep track of which paths earn the same n or m or l over time and also where the consecutive ones were. I then found that certain consecutive merges have the same pattern as others, like the 3 groups I found; the first one has 8n+4, 32n+20, 128n+84… the next has 16m+12, 32l+28, the last I found was 16m+2, 32l+18… all plus one for their pairs. The first two were 6 paths apart and the last one was 10.
This should contain all merges and could be a useful tool.
One thing I noticed about this was that the only coefficients of l or m or n smaller than 6 on this entire graph are 2n+1, 4n+2, and 4m+3. The 421 loop is when n is 0 and from 4n+2 to 8n+4 then 8m+1 etc.
if a nontrivial loop did exist then just by chance one of the nodes that aren’t 6*2^k n+4^k+1, one of the ones that needs the mod checked randomly is the same amount as 6n+4. It wouldn’t look like 6n+4, but something like 4096f+456 for example since n>m>l>>f I guess. Maybe by proving this can’t happen we can rule out loops, but it might just bring us back to what we already know about loops
As far as I know, there’s at least a 12.5% chance that m+1 merges with m, prohibiting m+1 from being in the same or a different cycle. In this case, if m is in a cycle, m+1 will merge and eventually iterate back to m, but m+1 can’t be in the cycle because it represents a different prefix to the merging point. It couldn’t be in a different cycle because it must iterate to m, but m would be in a different cycle.
The most common class of consecutive merging numbers are those who start with the same number of consecutive (3n+1)/2 steps, then go ‘01’ and ‘100’ respectively. At that point they merge. As this is for the pair (n, 2n+1), the small adjustment of multiplying the first number by two essentially makes this an (m, m+1) pair.
Let’s break this up by case:
Case 0 mod 4: ‘00’ - This doesn’t match the pattern of a merging pair
Case 1 mod 4: ‘10’ - This potentially matches m+1
Case 2 mod 4: ‘01’ - This potentially matches m (which remember is 2n)
Case 3 mod 4: ‘11’ - This potentially matches m+1
If a case potentially matches the vector for m or m+1, it has a 50% chance of realizing that potential. This is because any number that breaks its initial increasing streak with one even step is ‘type n’, and with two or more even steps is ‘type 2n+1’. Since, with reference to the original question of this thread, we only care if a number is ‘type m’ (which is any number that is twice a ‘type n’), then we only care about case 2 mod 4. If this ‘01’ continues with ‘01’, it’s a ‘type m’. If it continues with ‘00’, it isn’t. If it continues with ‘1’, we have the same ‘01’ or ‘00’ split, just with a longer prefix. Therefore case 2 mod 4 has a 50% chance of being ‘type m’. Since any number has a 25% chance of being congruent to 2 mod 4, the total odds of a given number being ‘type m’, and therefore merging with m+1, is 1 in 8, or 12.5%.
There are other predictable classes of consecutive merging numbers, including ones where m can be congruent to 1 mod 4, but these are much rarer and wouldn’t increase the percentage by much. I believe these other classes occur when a merging pair of this class, after the merge, reaches a member of another merging pair in just the right way.
This is of course just one perspective. Maybe the cycle numerator for m+1 can’t be an integer if it is for m. Actually, the above argument can be understood in these terms too. Switching the prefix from ‘type m’ to ‘type m+1’ changes the cycle numerator by subtracting 3^x. So if β / (2^k - 3^x) is an integer, can (β - 3^x) / (2^k - 3^x) also be an integer? No, because 3^x is never divisible by (2^k - 3^x). Therefore if m has this type of prefix and is a cycle member, m+1 will not be a cycle member.
I agree that this makes sense, especially because the smallest consecutive merge is 8n+4 and 8n+5, which also gives that 1/8 chance to merge with itself+1. As the numbers get larger, however, the percentage of numbers that merge with the next number goes up as more merge patterns occur, like 98-102 all merging, taking up a 4/8 chance in that range. The average of each range keeps going up, but it seems to be unknown if the probability reaches one.
Your logic with how a merge in a loop occurs is about where I could get to, but I also tried to look at how the 2^(k+1) factor compares to the 2(3^x) factor, (from m,m+1 to n becoming (2^k+1)s +m, (2^k+1)s+m+1 to 2(3^x)s+n) because if a nontrivial cycle that has a consecutive merge in it that merges at one of its starting points, like if m became m at the same moment m+1 merged with m then the loop is a lot more constrained, because only one s equates the 2^(k +1)side with 2(3^x) for any path, typically not as an integer.
So it might be possible to rule that possibility out where m merges with m+1 at m, and then we could try a step before m, or a few steps, until enough is ruled out. It might also be possible to compare or combine the constraints for loop top or bottom with an assumption of a merge that is the length of a loop. Could a merge be exactly as long as a nontrivial cycle, in a cycle?
If a nontrivial cycle exists, then every path into it must not fall to 4-2-1. Consecutive merges will collapse to a single number, by definition of the merge, so showing how merges that are near a nontrivial loop must behave would be useful.
Pertaining to your comment on merges with m as 1 mod 4, I know that those would not work with this definition. The smallest merge is 8s+4 and 8s+5, and all other merges have a higher power of 2 next to the s. This can be verified by looking at the prehistory of 6n+4, or other methods. You likely meant that m could be 1 mod 4, like in the case of 101 and 102, but this example is actually 32s+5 and 32s+6, occurring once every 32, instead of once every 4. You can find the power of 2, their frequency, by taking 2 to the number of even steps plus one. It took 4 even steps to reach 58, so (2^(4+1)s+101 or 102), and this becomes 32s+5 by subtracting a multiple of 32, or by reducing mod 32.