Divide by 4 and multiply by 15

[Chris Miller]

TL;DR Summary

A simple Collatz variation that seems to work

For any positive integer x, if x is even x=x/4 else x=x*15+1 and repeat until x<=1. Integer division, of course. So really x=floor(x/4) or, better, x=x>>2. The sequences tend to be much longer than for the Collatz where you multiply by 3 and divide by 2. But can anyone find an integer that does not return to 1 (or 0) for this variation? Are there any other divisors and multipliers that appear to also work?

 

[Mark44]

Summary:: A simple Collatz variation that seems to work

For any positive integer x, if x is even x=x/4 else x=x*15+1 and repeat until x=1. Integer division, of course. So really x=floor(x/4) or, better, x=x>>2. The sequences tend to be much longer than for the Collatz where you multiply by 3 and divide by 2. But can anyone find an integer that does not return to 1 for this variation? Are there any other divisors and multipliers that appear to also work?

Found this one right away: 10
10 / 4 == 2
2 / 4 == 0
I didn't check any others

 

[Chris Miller]

Thank you. And right, though you could've just started with 2. I meant <= 1. Will correct my post. (You won't find one without a computer. I haven't yet managed to with.)

 

[Mark44]

This code checks the numbers 0 .. 199

for num in range(200):
   val = num
   print("num: ", num, "\t")
   while (val != 1 and val > 0):
    #  print (val, "\t")
      if (val % 2 == 0): val = val >> 2
      else: val = val * 15 + 1     
   print ("Final value of sequence: ", val, "\n")

Edit: I didn't realize that you changed your first post to ask about sequences that didn't end with 1 or 0.
I haven't done the analysis, but I would break the problem into cases.
Case 1: the starting number is divisible by 4; i.e., is of the form 4n.
Case 2: the starting number is of the form 4n + 2.
Cases 1 and 2 are the only cases where the number is even -- that make the if statement true.
Case 3: the starting number is of the form 4n + 1.
Case 4: the starting number is of the form 4n + 3.
I'm not sure that cases 3 and 4 are necessary, but I've included them because of the division by 4 that happens in the if clause. In either of these cases, the resulting number will be even, since we're multiplying an odd number by 15 (which results in an odd number), and then adding 1, making the result even, which could be of the form 4n or 4n + 2.

 

[Chris Miller]

No need for case checking beyond even or odd.

Your code looks right. I deliberately only tested odd numbers (3,5,7...) last night. It's exactly like the Collatz, except you integer divide by 4 (instead of 2), and you multiply by 15 (instead of 3) , and (as you pointed out) you can also end on 0 (or 1). Much longer series are generated. E.g., the integer 85565 ($14E3D) takes 27,957 iterations, ascends to a 246-bit integer before descending to <=1. And the integer 81533 ($13E7D) ascends to a 362-bit integer before descending to <=1 in 11,116 loops.

(You are correct, multiplication of two odds + 1 is always even.)

Also, there seem to be unlimited variations in which you multiply only after a fixed (level) number of sequential odd values, else always divide by 4. For normal Collatz (level 0) there are 2 divisions for every multiplication by 3 (2^2-1). Whereas for level 2 there are (a probable) 14 divisions for every multiplication by 268,435,455 (4^14-1), and for which the integer 42005 generated 9,037,228 unique intermediary values, the highest being 28516 bits, on its way to <=1. (These levels also work with division by 2, and different multipliers, of course.)

I'm kind of treating the Collatz the way I treat software bugs in trying to understand. Cast in a wider net or context or something, then look for similarities. I think I understand, a little better now, its amazing resistance to repeating numbers in series. I'm not much of a mathematician, and am hoping those who are and other programmers will tackle these extensions of the conjecture.

(Dividing by 8 and multiplying by 63 does not work, sees repetitions).

 

[Baluncore]

Here is a slightly different view. Starting with the traditional Collatz sequence.

The structure is more than a sequence, it is a tree of nodes. The sequence is the path taken from a randomly selected node, via other nodes, until it reaches the root node.
The Collatz conjecture is that there is only one tree and the root is at x = 1.

The even rule, x' = x/2; and odd rule, x' = 3x+1 direct the path through the tree.
Reversing the sequence shows that a node x can be reached from; x = 2x' or
from x = (x' – 1 ) / 3; but only when; ( x Mod 3 ) = 1.

Any node x, can be reached from above by descending a cascade of even nodes that when viewed from below, extends exponentially upward towards infinity.
Half of those even nodes can be reached via an odd node from below by;
x' = 3x+1; when it fulfils the requirement that ( x Mod 3 ) = 1.

No node has been found where the sequence is captured in a cycle. That would require there be a separate ring structure. The cycle with it's infinite skyward branches would be floating somehow between the skyward branches of the root tree.

No node has been found that does not end at x = 1. If there was a set of nodes that skipped 1 and so ended at zero, it would be prohibited by the only mode of descent
which is the x' = x/2 rule.Now, the modified Collatz sequence. Even rule; x' = x \ 4; and odd rule x' = 15x+1.

Since the even rule; x' = x / 4; can take two steps of /2, it is possible to skip 1 and reach the root x = 0.
There are therefor two quite separate trees, one rooted in 0, the other rooted in 1. Those two trees have branches reaching skyward, towards infinity.

Reversing the sequence shows that a node x' can be reached from; x = 4x' or from; x = 4x'+2. In the second case, a binary bit may be lost without consideration of it's presence.
Node x' can also be reached from below, but only when; ( x Mod 15 ) = 1.

There may be floating cycles present with skyward branches, suspended between the skyward branches of the two identified trees.

 

[Baluncore]

Odd rule, x' = kx+1; and even rule, x' = x/2.
Collatz has k = 3;
If k = 1; then the sequence is so well behaved that it is obviously a single binary tree.

 

[Chris Miller]

Hey Baluncore! I'm glad to run into someone who's interested in the Collatz the way you are. I'm trying to get my head around your tree approach. And not really seeing it. To me it looks like a linked list. Every "node" x in the series has a pointer to a next node x, but not (unambiguously) to a previous node x. So the list can only be traversed in one direction. That these linked lists never form a ring before reaching 1 (for a 1,4,2,1... ring) (or 0..., for a ring of one node pointing to itself) is what's so mystifyingly demonstrable but un-provable. Especially where, in extended variations, the list is many billions of elements long and reaches million-bit values. It appears that one can increase the probable number of divisions (d) by 2 (or 4) per multiplication arbitrarily (by retesting for consecutive odds) as long as one then multiplies by 2^d-1 (or 4^d-1). As shown by your k=1 example, one wonders if, in the extended variations, multiplying by any odd number less than 2^d-1 will also always work (though probably result in shorter lists). It has in my limited testing.

There might be rings "floating branches" in the normal Collatz, too. But if there are, I'm guessing they're in integers too large to test.

 

[Chris Miller]

You k=1 variation is indeed interesting, and would seem to be provable!

 

[Baluncore]

So the list can only be traversed in one direction.

How to generate the tree backwards. Consider k = 1. The first few generations are ...
1. is the root of the tree.
2. The stop marks the end of a generation.
4.
8, 3. The comma separates even rule, from odd rule, where odd is possible.
16, 7; 6. The semicolon separates nodes in the previous generation.
32, 15; 14; 12, 5.
64, 31; 30; 28, 13; 24, 11; 10.
128, 63; 62; 60, 29; 56, 27; 26; 48, 23; 22; 20, 9.
256, 127; 126; 124, 61; 120, 59; 58; 112, 55; 54; 52, 25; 96, 47; 46; 44, 21; 40, 19; 18.

For example, the 8 can be reached by even rule from 16, or odd rule from 7.
3 can only be reached by even rule from 6.

For k = 1; it looks like all numbers appear only once.
Each generation is one step further from the root.

The population count of each generation; 1, 1, 2, 3, 5, 8, 13, 21,,,
That looks like it might be the Fibonacci numbers. Φ = 1.618033;
But each generation rises to twice the previous generation. 2.000;

Edit: The Fibonacci numbers hold at least as far as the 39th generation, when my crude program threw a "segmentation violation" error.
In the 39th gen there were; F39 = 63,245,986 members exactly.

 

[Chris Miller]

I see now that by a tree, you're mapping every possible linked list upwards from its terminus at 1. Obviously not possible where the other end ascends to infinity, but, in the case of k=1, an interesting tree. Not surprised to see Fibonacci orderliness. It's trivial to prove that your Collatz k=1 variation always reduces to 1 for any n without repetition of values. Take any integer M and divide while even. With M now odd, the next element is N=(M+1)/2. The only time M=N is if M=1, else M>N. Therefore any M will reduce to 1 for k=1.

Your approach to the Collatz via a provable k=1 variation might offer insight into the k=3 standard. I went the other way.

Looks like the number of nodes in level x+1 is the sum of the nodes in x and x-1. Very Fibonacci!

 

[Baluncore]

First an example of a cycle. Consider k = 5; Even rule x' = x/2; Odd rule x' = k·x + 1.
This demonstrates an isolated ring that traps the sequence.
{ 26, 13, 66, 33, 166, 83, 416, 208, 104, 52 }, { 26 …
It circulates with a minimum of 13, but can be entered via 5.

Re: The binary view when k = 1. I originally considered this because of the speed in a binary computer. It turns out to be so simple that it does not need a computer.
The even rule removes a least significant zero.
The odd rule increments the number, converting it to an even number.
The odd rule generates a carry ripple that flips all sequential ones on the right to 0s.
Each consecutive block of ones takes one application of the odd rule to convert it to zeros.

Re: k > 3. Since multiplication is a shift and add process, a multiply followed by the increment extends the number by the length of the multiplier. Following the increment there is then a 100% chance of the even rule removing one zero, and a 50% chance of removing another, decreasing. The break-even appears to be k = 3; beyond which the even rule cannot control the growth within a reasonable time, which makes following the sky-high sequences difficult.

I think an even rule that always shifts by more than 1 bit, for example; x' = x / 4; is unnecessary. It is needed when k, the odd multiplier, is unnecessarily large. Multiple unconditional right shifts permit a skip over 1, which forces a second tree rooted at zero. Analysis of the sequence becomes very complex when some bit values are ignored. You might as well define an even rule, x' = x / 256 to clear even bytes quickly. It changes the game and the analysis away from Collatz sequences.

 

[Chris Miller]

The only k's I've tested were d^ 2 - 1 where d was the probable number of divisions per multiplication. E.g., for level 2 where evens and the next 2 odds are divided (right shifted >>1) before only a 3rd sequential odd is multiplied, d=14, and so k=16383, which is the maximum value if you expect the series to eventually reduce. Lower odd values might work. The k=15 with x/4 is just a variation of level 1 where d=6, and so k=63. If reducing to either 0 or 1 confuses, forget the x/4 variant and quit as soon as any x=x/2 = 1 for any level.

With Collatz's even rule x=x/2 and odd rule x=x*5+1, if the series did not repeat, it could ascend to infinity. For level 0 (plain Collatz), with a probable 2 divides for each multiply, 3 is the highest working multiplier, and your 1 is the lowest.

 

[pbuk]

With Collatz's even rule x=x/2 and odd rule x=x*5+1, if the series did not repeat, it could ascend to infinity.

There is a fairly convincing but not rigorous argument that no hailstone number sequence in this form ascends to infinity: at each ## x_n = x_{n-1} \times (2k + 1) +1 ## step there is a non-zero chance that ## x_n = 2^m ## which means that the sequence will collapse to ## 1 ##. In order to ascend infinitely therefore, this non-zero chance will have to be avoided an infinite number of times. This is enough to convince me that any counter-example to the Collatz conjecture must end in a cycle, but as we do not have a model of probability theory that deals with infinities (and even if we did we would still have to deal with the fact that the process is clearly non-random) we cannot prove this.

 

[Chris Miller]

I've seen that argument as proof the Collatz itself is false. But as n approaches infinity 1/2^n (even more rapidly) approaches zero. A closed loop (which you seem to have shown via k=5) is more probable. But if k is odd and k <= 2^d-1 where d is the probable number of divides per multiply (2 for normal Collatz) so far, all variations appear to work.