# Collatz Conjecture (3n+1) variant

Let's consider the following variant of Collatz (3n+1) :

if $n$ is odd then $n \to 3n+1$

if $n$ is even then you can choose : $n \to n/2$ or $n \to 3n+1$

With this definition, is it possible to construct a cycle other than the trivial one, i.e., $1\to 4 \to 2 \to 1$?

Best regards

• This is a very interesting question. But trivially you can always avoid the 4->2->1 cycle, cause you always have the choice to jump. This means you either constructed a new cycle, escaleted to infinty or entered a non-periodic "cycle"/iteration. But on the other hand with this variant you can easily escalate to infinity, because you can always choose 3n+1. You can also construct non-periodic infinite iterations, but those will have to escalate to infinity aswell, as the amount of permutations in a limited enviroment is finite. Dec 27, 2016 at 18:17
• See here: mathoverflow.net/questions/216358/…
– user371838
Dec 28, 2016 at 10:05

Yes! With the standard Collatz conjecture, every number must eventually end up at the cycle $4 \to 2 \to 1 \to 4 \cdots$ . This has been verified for all numbers up to $2^{60}$.

With your altered definition, you can start at $2$, apply $3n+1$ instead of $n/2$, and then continue like the standard Collatz again.

$$2 \xrightarrow{3n+1} 7 \to 22 \to 11 \to \cdots ,$$ you'll eventually end at $2$ again, since this is one of the verified cases.

$$7\to 22$$ $$22\to11$$ $$11\to34$$ $$34\to17$$ $$17\to52$$ $$52\to26\to13$$ $$13\to40$$ $$40\to20\to10\to5$$ $$5\to16$$ $$16\to8\to4\to2$$ $$2\to 3\cdot2+1=7$$

• Everything was calculated as in the standard Collatz problem except for the very last step. If you're asking how I came about this example, I knew that any number would eventually get down to $2$, which I could then have go to $7$. Dec 27, 2016 at 22:34
• Ah, thank you for clarification Dec 27, 2016 at 22:35
• @florence, You knew that any number would get down to 2? Isn't that equivalent to the Collatz conjecture? Dec 27, 2016 at 23:09
• @ZacharyT up to 10^60 or so. Good enough to find this counterexample. Dec 28, 2016 at 1:00

$4\to13\to40\to20\to10\to5\to16\to8\to4$

There are quite a few such cycles. Here's the list of all cycles of length $\le 30$ starting from any number $< 10^5$ that never exceed $2^{63}$:

[2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4]
[2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 13, 40, 20, 10, 5, 16, 8, 4]
[2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 49, 148, 74, 37, 112, 56, 28, 85, 256, 128, 64, 32, 16, 8, 4]
[2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4]
[2, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 61, 184, 92, 277, 832, 416, 208, 104, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4]
[2, 7, 22, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4]
[4, 13, 40, 20, 10, 5, 16, 8]
[4, 13, 40, 20, 10, 5, 16, 8, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8]
[4, 13, 40, 20, 10, 5, 16, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8]
[4, 13, 40, 20, 10, 5, 16, 49, 148, 74, 37, 112, 56, 28, 85, 256, 128, 64, 32, 16, 8]
[4, 13, 40, 20, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8]
[4, 13, 40, 20, 61, 184, 92, 277, 832, 416, 208, 104, 52, 26, 13, 40, 20, 10, 5, 16, 8]
[5, 16, 8, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10]
[5, 16, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10]
[5, 16, 49, 148, 445, 1336, 668, 334, 167, 502, 1507, 4522, 2261, 6784, 3392, 1696, 848, 424, 212, 106, 53, 160, 80, 40, 20, 10]
[5, 16, 49, 148, 445, 1336, 668, 2005, 6016, 3008, 1504, 752, 376, 188, 565, 1696, 848, 424, 212, 106, 53, 160, 80, 40, 20, 10]
[7, 22, 11, 34, 103, 310, 155, 466, 233, 700, 2101, 6304, 3152, 1576, 788, 394, 197, 592, 296, 148, 74, 37, 112, 56, 28, 14]
[7, 22, 11, 34, 103, 310, 931, 2794, 1397, 4192, 2096, 1048, 524, 262, 131, 394, 197, 592, 296, 148, 74, 37, 112, 56, 28, 14]
[7, 22, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 265, 796, 2389, 7168, 3584, 1792, 896, 448, 224, 112, 56, 28, 14]
[7, 22, 67, 202, 101, 304, 152, 76, 38, 115, 346, 173, 520, 260, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14]
[7, 22, 67, 202, 101, 304, 152, 76, 229, 688, 344, 172, 86, 43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14]
[8, 25, 76, 38, 19, 58, 29, 88, 44, 133, 400, 200, 100, 50, 151, 454, 227, 682, 341, 1024, 512, 256, 128, 64, 32, 16]
[8, 25, 76, 38, 19, 58, 29, 88, 44, 133, 400, 200, 100, 301, 904, 452, 226, 113, 340, 170, 85, 256, 128, 64, 32, 16]
[8, 25, 76, 38, 19, 58, 29, 88, 265, 796, 2389, 7168, 3584, 1792, 896, 448, 224, 112, 56, 28, 85, 256, 128, 64, 32, 16]
[8, 25, 76, 38, 115, 346, 173, 520, 260, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 85, 256, 128, 64, 32, 16]
[8, 25, 76, 229, 688, 344, 172, 86, 43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 85, 256, 128, 64, 32, 16]
[10, 31, 94, 47, 142, 71, 214, 643, 1930, 965, 2896, 1448, 724, 362, 181, 544, 272, 136, 68, 34, 17, 52, 26, 13, 40, 20]
[11, 34, 17, 52, 26, 13, 40, 20, 61, 184, 92, 277, 832, 416, 208, 625, 1876, 938, 469, 1408, 704, 352, 176, 88, 44, 22]
[11, 34, 17, 52, 26, 13, 40, 121, 364, 182, 91, 274, 137, 412, 1237, 3712, 1856, 928, 464, 232, 116, 58, 29, 88, 44, 22]
[11, 34, 17, 52, 26, 13, 40, 121, 364, 182, 547, 1642, 821, 2464, 1232, 616, 308, 154, 77, 232, 116, 58, 29, 88, 44, 22]
[11, 34, 17, 52, 26, 13, 40, 121, 364, 1093, 3280, 1640, 820, 410, 205, 616, 308, 154, 77, 232, 116, 58, 29, 88, 44, 22]
[11, 34, 17, 52, 26, 79, 238, 119, 358, 179, 538, 269, 808, 404, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22]
[11, 34, 17, 52, 157, 472, 236, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22]
[11, 34, 17, 52, 157, 472, 236, 118, 355, 1066, 533, 1600, 800, 400, 200, 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22]
[11, 34, 17, 52, 157, 472, 236, 709, 2128, 1064, 532, 266, 133, 400, 200, 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22]
[13, 40, 20, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 61, 184, 92, 277, 832, 416, 208, 104, 52, 26]
[13, 40, 20, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 241, 724, 362, 181, 544, 272, 136, 68, 34, 17, 52, 26]
[13, 40, 20, 61, 184, 92, 277, 832, 416, 208, 104, 52, 26]
[14, 43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28]
[14, 43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 85, 256, 128, 64, 32, 16, 49, 148, 74, 37, 112, 56, 28]
[16, 49, 148, 74, 37, 112, 56, 28, 85, 256, 128, 64, 32]
[19, 58, 29, 88, 44, 22, 67, 202, 101, 304, 152, 76, 38]
[19, 58, 29, 88, 44, 133, 400, 200, 100, 50, 25, 76, 38]
[20, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40]


It was generated by the following Java program:

public class ModifiedCollatz {

int maxLength = 30;

long[] currentPath = new long[maxLength];

void find() {
for (int i = 2; i < 100_000; i++) {
find(i, i, 0);
}
}

void find(long a, long goal, int depth) {
if (depth >= maxLength || a < goal) {
return;
}

if (depth > 0 && a == goal) {
System.out.println(Arrays.toString(Arrays.copyOf(currentPath, depth)));
return;
}

currentPath[depth] = a;
if (a % 2 == 0) {
find(a / 2, goal, depth + 1);
}
find(3 * a + 1, goal, depth + 1);
}

public static void main(String[] args) {
new ModifiedCollatz().find();
}
}


$$8 \rightarrow 25 \rightarrow 76 \rightarrow 38 \rightarrow 19 \rightarrow 58 \rightarrow 29 \rightarrow 88 \rightarrow 44 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8$$

And another one:

$$16 \rightarrow 49 \rightarrow 148 \rightarrow 74 \rightarrow 37 \rightarrow 112 \rightarrow 56 \rightarrow 28 \rightarrow 14 \rightarrow 7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16$$

Both avoid the 4, 2, 1 cycle.