Collatz Conjecture Revisited (part 2): 3n+3

I've previously looked at the Collatz conjecture, (3n+1) and I have revisited it before, too (5n+1).  Now, I would like to revisit it again.

The Collatz Conjecture states that when you take a number, and if it's even then divide by two, or if it's odd then multiply by three and add one, then you will eventually reach 1.  There's no proof (yet), but it holds for all numbers that have been tested.

I extended this in a previous post, and looked at the case of multiplying by five (instead of three) and adding one, and identified two loops and a growing series.

In this post, I will share my findings on another alternative, which is "3n+3".  [3n+2 doesn't work, since if n is odd, then 3n + 2 will also be odd].

3n+3

3n+3 has one loops which covers all numbers I have tested.

The simple loop/termination is [1], 6, 3, 12, 6, 3, 12.

There are various ways into this loop, in particular,
10, 5, 18, 9, 30, 15, 48, 24, 12, 6, 3, 12 etc.
7, 30, 15, 48 etc.
11, 36, 18, 9, 30, 15, etc.
13, 42, 21, 66, 33, 102, 51, 156, 78, 39, 120, 60, 30, 15, etc.

Interestingly, many of the starting numbers reach a common maximum value of 27696 before coming back down to 1.    This is first seen for an initial n=53.

For larger values of n, there is a longer sequence.  The graph below shows the maximum value of n (vertical axis) for different start values of n (between 101 and 241, as example material).  Note how 27696 predominates as the largest value reached.

The sequence from 27696 is:

27696, 13848, 6924, 3462, 1731, 5196, 2598, 1299, 3900, 1950, 975, 2928, 1464, 732, 366, 183, 552, 276, 138, 69, 210, 105, 318, 159, 480, 240, 120, 60, 30, 15, 48, 24, 12, 6, 3

27696 is seen for the following initial values of n:

53, 61, 81, 93, 107, 109, 123, 125, 141, 145, 163, 165, 181, 187, 189 (and others).

For values above 27696
I have not explored extensively above 27696, but there is a cluster of initial values that have the same new peak.  The cluster is around 27754:  27754, 27755 and 27757 all have the same maximum, which is 2026128.  The highest peak I have observed so far is for 27729, which reaches a height of 2698752.

To close, the full sequence for 27729 is:

27729, 83190, 41595, 124788, 62394, 31197, 93594, 46797, 140394, 70197, 210594, 105297, 315894, 157947, 473844, 236922, 118461, 355386, 177693, 533082, 266541, 799626, 399813, 1199442, 599721, 1799166, 899583, 2698752, 1349376, 674688, 337344, 168672, 84336, 42168, 21084, 10542, 5271, 15816, 7908, 3954, 1977, 5934, 2967, 8904, 4452, 2226, 1113, 3342, 1671, 5016, 2508, 1254, 627, 1884, 942, 471, 1416, 708, 354, 177, 534, 267, 804, 402, 201, 606, 303, 912, 456, 228, 114, 57, 174, 87, 264, 132, 66, 33, 102, 51, 156, 78, 39, 120, 60, 30, 15, 48, 24, 12, 6, 3

I shall continue to explore 3n+3, and also too compare the data and sequences with 3n+5.

My articles on the Collatz Conjecture:

Snakes and Ladders (an introduction to the Collatz Conjecture)
Collatz: 5n + 1
Collatz:  3n + 3
Collatz: 3n + 5
Generative AI proves the Collatz Conjecture (published 1 April 2024)

Revisited: The Collatz Conjecture 5n+1

In a previous post, I've outlined and explained the Collatz conjecture - take a real, positive number, and if it's odd multiply by three and add one; if it's even, divide by two, and repeat until you reach one.  The sequence terminates at 1, although it's not yet been proved for all numbers (just a lot of them).

But what happens if we change the rules of the sequence, and divide by two for even numbers, but multiply by FIVE and add one for odd numbers?  So instead of 3n+1 the next term is 5n+1.  My searching on the internet has not identified anybody who has previously followed this line of research, so I have decided to pursue it.

A variation on the Collatz Conjecture:  5n+1

For the Collatz conjecture, all series reach one (or so it seems, there's no formal proof yet).  However, if we follow a new algorithm, and multiply by five and add one for the odd numbers, we enter one of a number of different scenarios (I've identified four,but this is not conclusive or exhaustive).

Firstly, trying this variation of the Collatz series, starting with 1.  Seems like a good place to start, and it's not as trivial as the original series.  Starting with 1 produces a loop:

1 -- 6 -- 3 -- 16 -- 8 -- 4 -- 2 -- 1 which is the simplest loop, "Loop A" and contains 1, 2, 3 and 4.


Secondly:  (5 -- 26 --) 13 -- 66 -- 33 -- 166 -- 83 -- 416 -- 208 -- 104 -- 52 -- 26 -- 13 which is another loop, "Loop B"


So far, this covers 1, 2, 3, 4, 5 and 6, 8, and 10 (which divides by two to enter Loop B).

Thirdly:  However, something that I found strange and unexpected happens if we start with 11 (which goes through 7 after four steps, and 9 after seven steps)

Observations:

*  The series does not appear to enter a loop, it just keeps growing and growing - although I can't prove it.
*  The odd numbers that series includes are either prime - shown in red - or semi-prime (only having prime factors), shown in blue.
*  The first non-prime in the series is 9, which is the square of a prime (3).

The fourth variation I've seen starts with 17.  It seems that there's no pattern for other odd numbers which have not been in the previous loops, so I'm working through them.  For example, 15 enters the growing sequence at 46 (in the top row of the diagram of the sequence shown above), but 17 enters a different loop, Loop C.

Summary:

The 5n+1 variation of the Collatz conjecture leads to one of four situations:

Loop A:  1 - 6 - 3 - 16 - 8 - 4 - 2 - 1
Loop B:   (5 - 26 -) 13 - 66 - 33 - 166 - 83 - 416 - 208 - 104 - 52 - 26 - 13
Loop C:  17 - 86 - 43 - 216 - 108 - 54 - 27 - 136 - 68 - 34 - 17
Sequence:  Starting with 11 (and including 7 and 9) - limitless growth (it does not appear to enter a loop)

Future developments: 

*  To look for additional loops, continuing to review the prime numbers not already covered.
*  To try another variation on the Collatz Conjecture, for example, 5n-1 instead of 5n+1.  Clearly, 5n+1 has the scope to grow very rapidly with almost no chance of decreasing, and the only observations that can be made are on the numbers that the sequence goes through.

My articles on the Collatz Conjecture:

Snakes and Ladders (an introduction to the Collatz Conjecture)
Collatz: 5n + 1
Collatz:  3n + 3
Collatz: 3n + 5
Generative AI proves the Collatz Conjecture (published 1 April 2024)

Puzzle: Snakes and Ladders

(also known as the Collatz conjecture, or Syracuse problem)


Courtesy of Calculator Fun and Games, which first introduced me to it, here's an interesting puzzle that is easy enough to understand, but which has developed into a far more complicated problem.  In fact, if you want to make the easy idea hard to understand, just go and read the Wikipedia entry - it is far too complicated, as much of maths on Wikipedia tends to be.


Anyway, here it is: Take a number - any number.  If it's odd, multiply by three and add one.  If it's even, divide by two.  Now take your new number and follow the same process - odd numbers multiply by three and add one, even numbers divide by two.  And so on, and so on.  

What do you find?  And, more importantly, does this always happen?


Let's try a few numbers:
35 is odd, so multiply by 3 ( = 105) and then add 1 = 106
106 is even, so divide by 2 = 53
53 is odd, so multiply by 3 (=159) and then add 1 = 160
160 is even, so divide by 2 = 80
80 is even, so divide by 2 = 40
40 is even, so divide by 2 = 20
20 is even, so divide by 2 = 10
10 is even, so divide by 2 = 5
5 is odd so multiply by 3 and add 1 = 16
16 is even, divide by 2 = 8, which is also even, divide by 2 = 4, then 2, then 1.


If (or should that be "When"?) you reach 1, then you stop.  Otherwise, you get stuck in a loop that goes 1 -- 4 -- 2 -- 1 -- 4 -- 2 etc.


The question is:  Do you always reach 1?  Is there a number out there somewhere that doesn't eventually drop down to 1?


The path length for numbers (how long it takes for a number to reach 1) is not predictable - certainly not easily, as far as I know, and so there's much research there as well.


For example, 26 follows the path 26 - 13 - 40 - 20 - 10 - 5 - 17 - 8 - 4 - 2 - 1


But 27 follows a completely different path...
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077,9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1


...with its highest point at over 9,000!  All in all, it has 111 steps in its path to 1.

Image from Calculator Fun and Games
(original was black and white line drawing)

Here are the paths for all the numbers 1-20 (and the numbers that they include):

Image from: "Professor Stewart's Hoard of Mathematical Treasures"

There are various puzzles connected with this problem.  The main one is to prove that all paths end at 1, but that's still not been completely solved yet, and some of mathematics' greatest minds are having a go.

A good alternative, though, is to find the longest path possible for three-digit and four-digit figures.  I'm not sure if it's a puzzle, or a game, and if it's a game, then I figure it'd probably spoil it for you to know the answer before you start :-)

This was my first post on the Collatz conjecture, but I enjoyed investigating it so much that I wrote (and continue to write) a series of articles about variations on it, and you can find them in my Collatz conjecture category.  The next article in the series is Collatz Conjecture 5n+1 and after that, Collatz Conjecture 3n+3.