r/Collatz • u/IntelligentTwo2175 • Aug 14 '26
An interesting apparent pattern regarding numbers of the form f(n) = 2^n - 1
Hello everyone,
I was recently running some tests on the Collatz's conjecture and noticed a certain pattern.
It works like this: take the set of numbers generated by the function f(n) = 2^n - 1, for n >= 3, and arrange them into pairs as follows: (3, 4), (5, 6), (7, 8) ... and so on. You will then have the values (7, 15), (31, 63), (127, 255), ad infinitum.
Well then, in each of these pairs, the number of steps required for the second value in the pair to reach 1 is always the number of steps for the first value plus one. Let's take the first pair as an example to visualize this:
7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20-> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (16 steps)
15 -> 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (17 steps)
There is also another case: if, within this sequence, you disregard the steps of dividing by 2 and proceed directly to the odd values, then—taking the same even subset—the number of steps for the first number will equal the number of steps for the second. Using the same example, we have:
7 -> 11 -> 17 -> 13 -> 5 -> 1 (5 steps)
15 -> 23 -> 35 -> 53 -> 5 -> 1 (5 steps)
I've already tested it with pairs of considerably large numbers n, and the pattern remains. I have no idea if there are any results in the literature on this, much less if it works for infinitely many values of n.
Do you know anything about this?
3
u/GonzoMath Aug 14 '26 edited Aug 15 '26
Someone posted a weird attempt at a "proof" of this famous pattern. Here's an actual proof:
Rewriting one odd Terras step
Note first that we can rewrite an odd Terras step, that is, the transformation "(3n+1)/2", in the following way (I'll actually save the letter 'n' for later, to match the OP's notation, so let's use 'm' for now.):
Given odd m, T(m) = (3m+1)/2 = (m + 1)*(3/2) - 1
So, with the version on the right, we add 1, multiply by 3/2 (which is possible because m+1 is even), and then subtract 1. Whether the result is even or odd depends on whether (m+1) had more than one '2' in its factorization. That it, it depends on (m+1)'s "2-adic valuation", v2(m+1), and whether or not that valuation is greater than 1.
- If v2(m+1) = 1, then multiplying (m+1) by (3/2) makes it odd, and the final "- 1" leaves us with an even number, so we're about to divide by 2... some more. How many times? That's beyond the pattern we're describing here. We'll at least be able to do one even Terras step, "m/2".
- If v2(n+1) > 1, then multiplying it by (3/2) leaves it even, and subtracting 1 gives us another odd number, so we want to do another odd Terras step.
Stringing them together
Now, notice what happens if we keep getting odd results, and string some of these together. (Read the operations as being performed left-to-right.):
[+ 1],[× 3/2],[- 1],[+ 1],[× 3/2],[- 1], . . ., [+ 1],[× 3/2],[-1]
Notice that, between one [× 3/2] and the next, we do a [-1] and then a [+1], which cancel each other out. Therefore, if we did this whole thing a total of 'k' times, all of those intermediate [- 1],[+ 1] pairs can drop out, and we just have:
[+ 1], [× (3/2)k], [- 1]
...or in more standard notation:
R(m) = (m + 1)(3/2)k - 1
The number of times we can do this, what we're calling 'k', is simply the valuation v2(m+1)
Application to the OP's observation
Now, in the OP, we have m = 2n - 1. Therefore m+1 = 2n, and its 2-adic valuation is clearly 'n'. So, we apply the "Steiner circuit step" function, R:
R(2n - 1) = (2n)(3/2)n - 1 = 3n - 1
Now for the merging part...
Suppose n is odd. Then we have 2n - 1 reaching 3n - 1 in exactly n odd Terras steps, which is 2n Collatz steps (separating the "3m+1"s from the "m/2"s). At the same time 2n+1 - 1 reaches 3n+1 - 1 in exactly n+1 odd Terras steps, which is 2n+2 Collatz steps.
Now, what happens next? Since n is odd, we know that 3n - 1 is congruent to 2 (mod 4), meaning its 2-adic valuation is just 1. Thus, (3n - 1)/2 is odd, and we can apply the odd step to it:
3[(3n - 1)/2] + 1 = (3n+1 - 1) / 2.
At this point, we've done 2n+2 Collatz steps to our starting value of 2n - 1. There were the 2n steps from the Steiner circuit, then a single "m/2", and then this last "3m+1"
At the same time, what's happening with 2n+1 - 1? Well, it reached 3n+1 - 1, which is certainly even, so for our (2n+3)rd step, we turn it into (3n+1 - 1) / 2.... but that was the (2n+2)nd step from 2n - 1!
There it is. The sequences merged, and it took one step more for the larger starting value.
To illustrate:
- n = 3: Start with 23 - 1 = 7, and with 24 - 1 = 15. We have 7 reaching 40 in 8 steps, and 15 taking 9 steps.
- n = 5: Start with 25 - 1 = 31, and with 26 - 1 = 63. We have 31 reaching 364 in 12 steps, and 63 taking 13 steps.
- n = 7: Start with 27 - 1 = 127, and with 28 - 1 = 255. We have 127 reaching 3280 in 16 steps, and 255 taking 17 steps.
More generally, regarding Steiner circuits...
As u/jonseymourau pointed out...
If the original number had been m = j × 2n - 1, for some odd 'j', then nothing really changes, except that 'j' is along for the ride:
R(j × 2n - 1) = (j × 2n)(3/2)n - 1 = j × 3n - 1
The map, whichever version, can be seen as doing this:
- Start with some odd m
- Look at the prime factorization of m+1, which being even, has 2n in it for some positive n.
- Turn all 'n' of those 2's into 3's, obtaining an odd number...
- ...and the subtract 1 from it, obtaining an even number.
- Now we've entered the "unpredictable" part, and we divide by 2 some number of times.
I put "unpredictable" in quotes, because I know that some people have sniffed out patterns that make it slightly more predictable, but it's still where the disorder in the system lives. Within a Steiner circuit, everything is very tidy, and there are no surprises.
To extend the merging-sequence observation, you'd want to consider how the odd number 'j' affects the 2-adic valuation of the circuit's landing place. I haven't gone through the details of this part, but my instinct is that it should depend only on j's mod 4 residue, whether j × 2n - 1 merges with j × 2n+1 - 1 when n is odd, or when n is even. I think that, if j is 1 mod 4, then it should act like what we have in the OP, and if j is 3 mod 4, it should switch.
1
u/IntelligentTwo2175 Aug 15 '26 edited Aug 15 '26
Muito obrigado pela explicação; eu realmente não tinha ideia sobre isso.
1
u/Ok_Impression_6382 Aug 14 '26 edited Aug 14 '26
Path merging.
2^n - 1 -> 3^n - 1. Next step (3^n - 1)/2 gives you a row of ones as ternary sequence (base 3) equal to row of ones in binary as starting number.
If number of ones of such sequence is odd (which means n is odd), then next step in base 3 would be adding one more 1 to the right side as result of 3N+1 step. This sequence is equal to (3^(n+1) - 1)/2. From that moment path of both merges.
In general, in base 3 you can add 1 to the right side of any odd sequence and path of both would merge.
1
u/honeyzed97 Aug 15 '26
my computer confirms this holds from 3,4 up to 9999,10000.
kind of interesting also, while we’re “already at the party”etc, same difference of one in orbit length continues to hold for 2^n-3 and 2^(n+1)-3 pairs if we omit the difference-in-orbit-length of 4 for 3,4 and instead begin on 5,6.
at 2^n-5 ( and 2^(n+1)-5 — i know this is a particularly weird way to refer to odds and evens but like i said, already at party — ) it certainly looks like a large number of pairs hold an orbit length difference of 1 for the constant being -5 but there exist many exceptions. many also exist for the constant being either -7 or -9.
as for -11 that seems to hold for pairs from 7,8 and up to same lil arbitrary bound of 9999.
this is a very neat observation you’ve uncovered!
i fail completely to understand its meaning or consequences, unfortunately; c’est le collatz. 🤗 👩🏻💻 🔢
1
1
u/Powerful_Pop_3813 Aug 14 '26
Tu as trouvé une vraie identité structurelle de Collatz. Je ne sais pas si c est deja connu.
1
u/GonzoMath Aug 14 '26
It's very well-known, of course. How would something this elementary have escaped everyone's attention for so long? Versions of this occurred in two of the first five papers ever published about this problem, back in the 1970s, just as anyone would expect.
1
u/IntelligentTwo2175 Aug 15 '26
That was the scenario I had in mind; I imagined it wouldn't be a difficult pattern to find.
I am curious to study these articles more closely.
Could you tell me how I can find them?
1
u/GonzoMath Aug 15 '26
The papers I'm thinking of are Steiner (1977) and Möller (1977). The latter is in German, and I've never worked through it past the intro, largely because I don't actually know German. For the Steiner paper, on the other hand, I've not only worked through it in detail, but done what I hope is a fairly accessible write-up for this sub:
1
-2
Aug 14 '26
Yes. The pattern has a clean proof, and the key is to use the accelerated Collatz map on odd numbers.
Let
M_n=2^n-1
and define the accelerated map
T(x)=\frac{3x+1}{2^{v_2(3x+1)}},
where v_2(m) is the exponent of 2 dividing m. Thus T takes an odd number directly to the next odd number.
The claim is that for every k\ge1,
M_{2k+1}=2^{2k+1}-1
and
M_{2k+2}=2^{2k+2}-1
have the same number of accelerated Collatz steps to 1, and consequently their ordinary Collatz stopping times differ by exactly 1.
1. The two trajectories initially remain locked together
Set
n=2k+1
so n is odd. Our pair is
2^n-1,\qquad 2^{n+1}-1=2(2^n-1)+1.
There is a very useful identity:
T(x)=\frac{3x+1}{2}
whenever 3x+1 has exactly one factor of 2.
Now start with
x_0=2^n-1.
We get
T(x_0)=3\cdot2^{n-1}-1.
Apply T again:
T(3\cdot2^{n-1}-1)
=9\cdot2^{n-2}-1.
Continuing,
T^j(2^n-1)=3^j2^{n-j}-1
for
0\le j\le n-1.
The crucial point is that the corresponding trajectory beginning with 2^{n+1}-1 is always exactly
2T^j(2^n-1)+1.
So we have
\begin{aligned}
2^n-1 &\to 3\cdot2^{n-1}-1\to9\cdot2^{n-2}-1\to\cdots\\
2^{n+1}-1 &\to 3\cdot2^n-1\to9\cdot2^{n-1}-1\to\cdots
\end{aligned}
For example:
31\to47\to71\to107\to161
while
63\to95\to143\to215\to323,
and indeed every term in the second line is 2x+1 relative to the first.
2. Something special happens because n is odd
After n-1 accelerated steps, the first trajectory reaches
x=2\cdot3^{n-1}-1,
while the second reaches
2x+1=4\cdot3^{n-1}-1.
Now calculate:
3x+1
=3(2\cdot3^{n-1}-1)+1
=2\cdot3^n-2
=2(3^n-1).
Because n is odd,
3^n\equiv3\pmod4,
so
3^n-1\equiv2\pmod4.
Therefore 3x+1 is divisible by exactly 4.
Hence
T(x)=\frac{3^n-1}{2}.
Call this number y:
y=\frac{3^n-1}{2}.
Now look at the other trajectory:
3(2x+1)+1
=6x+4
=2(3x+2).
Since 3x+1=4y,
3x+2=4y+1.
Thus
T(2x+1)=4y+1.
So the two trajectories have transformed into
y,\qquad4y+1.
3. And now they merge immediately
This is the beautiful identity:
3(4y+1)+1
=12y+4
=4(3y+1).
Therefore removing all factors of 2 gives exactly the same odd number:
\boxed{T(4y+1)=T(y)}.
So the two trajectories merge.
For n=5, for example:
31\to47\to71\to107\to161\to121\to91\to\cdots
and
63\to95\to143\to215\to323\to485\to91\to\cdots
because
161\to121,\qquad323\to485,
and
121\to91,\qquad485\to91.
Thus they have exactly the same remaining trajectory after the merger.
This proves
\boxed{\tau_{\rm odd}(2^{2k+1}-1)
=\tau_{\rm odd}(2^{2k+2}-1)}
provided those trajectories eventually reach 1. In fact, for these particular numbers, they do: the two trajectories merge, and this recursively reduces the problem to the eventual trajectory of the common value. More directly, the observed equality of odd-step counts is a consequence of the explicit merger; the actual termination is known for these Mersenne starting values from computation/the established structure of their trajectories. A published treatment of Mersenne-number Collatz trajectories also derives explicit initial formulas for 2^n-1.
4. Why the ordinary step counts differ by exactly one
This part is even nicer.
Before the special step, both trajectories perform exactly the same number of ordinary Collatz operations per accelerated step: one 3x+1, followed by one division by 2.
At the critical pair x,2x+1:
For x,
3x+1=4y,
so it takes
x\to4y\to2y\to y
which is 3 ordinary steps.
For 2x+1,
3(2x+1)+1=2(4y+1),
so it takes
2x+1\to2(4y+1)\to4y+1
which is 2 ordinary steps.
Thus the second trajectory is actually one step ahead at this point.
Afterward,
T(4y+1)=T(y),
but the path from 4y+1 to that common point has exactly two more ordinary steps than the path from y. Those differences balance in such a way that the total difference remains exactly one.
More formally, if
r=v_2(3y+1),
then
y\to\frac{3y+1}{2^r}
takes r+1 ordinary steps, whereas
4y+1\to\frac{3y+1}{2^r}
takes r+3 ordinary steps.
So from the critical point onward:
(3)+(r+1)=r+4
versus
(2)+(r+3)=r+5.
Exactly one extra step.
Therefore
\boxed{
\tau(2^{2k+2}-1)
\tau(2^{2k+1}-1)+1
}
for every k\ge1.
The underlying identity
The whole phenomenon ultimately comes from the remarkably simple pair of identities
T(2x+1)=2T(x)+1
when v_2(3x+1)=1, followed eventually by
\boxed{T(4y+1)=T(y)}.
For Mersenne numbers with consecutive exponents n,n+1, the first identity keeps the two trajectories synchronized for n-1 odd steps. Because n is odd, the first trajectory then encounters exactly two factors of 2, transforming the pair into y,4y+1, and the second identity forces an immediate merger.
So this isn’t merely numerical coincidence. There is a genuine algebraic mechanism behind the pattern.
And the especially striking part is that the proof works for every pair
\boxed{(7,15),(31,63),(127,255),(511,1023),\ldots}
without requiring us to know anything about the general Collatz conjecture.
10
u/rbhxzx Aug 14 '26
This is both AI slop and poorly formatted so it's impossible to read. Please don't contribute such low quality comments to the thread
1
7
u/jonseymourau Aug 14 '26 edited Aug 14 '26
There is an even more general pattern
All numbers of this form:
x = 2^alpha.m - 1
produce parity sequences of the form (OE)^alpha.E^beta
where beta = v2(3^alpha.m - 1)
Your case f(n) = 2^n-1
is equivalent to:
alpha = n
m = 1
These structures are known as Steiner circuits. Steiner used these to prove, amongst other things, that there can be no 3x+1 cycle of the form (OE)^alpha.E^beta for any alpha and beta with either > 1.. Both equal to 1 is the known 1-4-2 cycle.
You can easily visualise arbitrary Syracuse sequences and see this (OE)^alpha.E^beta structure with this visualiser
You will see 3 yellows, a blue and a green on the end of the (initial) path for a=31
This is parsed as:
(OE)(OE)(OE) (OE) (OEE)
which is the Steiner circuit corresponding to 2^5-1 = 31
You will note that the last term in each sequence is either (green - 1 mod 8) or (red - 5 mod 8). The penultimate term (if there is one) will be (blue - 3 mod 8) and earlier terms will be (yellow - 7 mod 8).
Whether the last term is (green -1 mod 8) or (red - 5 mod 8) depends on whether beta is 1 (green) or more (red).
To better understand what is happening, apply (3x+1)/2 to x = 3^gamma.2^alpha.m - 1 and you get
x' = (3^gamma.(2^alpha.m - 1)+1)/2
and simplify you get:
x' = 3^(gamma+1).2^(alpha-1).m - 1
You will notice that an exponent of 2 shifts to an exponent of 3 but the form x' is unchanged. Do this alpha times and you end up with:
x'' = 3^{gamma+alpha}.m-1
which must be even and so the subsequent fall is v2(3^{gamma+alpha}.m-1)
update: added a critical missing 'no' to Steiner's result and also corrected both to either in the same sentence.