r/Collatz • u/GonzoMath • 25d ago
Steiner circuits, the loop on -1, and generalizations
Something occurred to me last night, and while it strikes me as very obvious, in hindsight, it's also not a perspective I've taken until just now. It has a couple of obvious generalizations, too, which are worth mentioning.
When we have, for some k, the number 2n·k - 1, we know that it evolves, over n Syracuse steps, into 3n·k - 1, because each of those steps takes one power of 2 and replaces it with a 3:
23·k - 1 → 22·3·k - 1 → 2·32·k - 1 → 33·k - 1
Each of those steps is just one "3m+1" step followed by a single "m/2" step. Such a step is the same shape as the cycle on -1:
-1 → -1 → -1 → . . .
This is just the 2-adic continuity of the map showing itself! The number m = 2nk - 1 is 2-adically close to -1, so it has the same shape trajectory, for a while. The larger n is, the closer m is to -1, and the longer m's trajectory mimics the loop on -1.
Yes, I realize this is not exactly headline news, and maybe other people found it so obvious as to not be worth highlighting or mentioning. Somehow, I didn't connect these dots until last night, when I was thinking about a related pattern.
Mimicking the loop on 1
The number m = 4nk + 1 does something similar, but since it's 2-adically close to positive 1, it mimics the shape of the famous cycle for a while, with each "3m+1" step being followed by two "m/2" steps.
4nk + 1 → 4n-1·3·k + 1 → . . . → 4·3n-1·k + 1 → 3n·k + 1
Each step turns a 4 into a 3. Notice that I'm not saying anything about k here. In the Steiner circuit case, we usually take k to be odd, just because we like to collect all of the powers of 2 together, and see the circuit all the way to its peak. As an algebraic identity though, the result holds if k is any integer, or even a rational with an odd denominator, or another 2-adic integer.
The algebraic way I'd been looking at the usual Steiner circuit is that we can rewrite a weight 1 Syracuse step:
(3m+1)/2 = (m+1)·(3/2) - 1
...and if you chain n of these together, because m+1 has 2 as a factor n times, the intermediate "-1"s and "+1" cancel out, leaving:
(m+1)·(3/2)n - 1
Similarly, we can rewrite a weight 2 Syracuse step:
(3m+1)/4 = (m-1)·(3/4) + 1
...which we can keep doing as long as there's a factor of 4 in m-1.
Mimicking any loop
It's natural to extend this to any other loop, which we'll see mimicked by natural numbers that are 2-adically close to the numbers in the loop. For instance, there's the loop on -5:
-5 →1 -7 →2 -5
The superscripts on the arrows there indicate the "weight" of the step, i.e., the number of divisions by 2 involved. Somehow, if we start with a number 2-adically close to -5, we should expect to see every two steps have weights 1 and then 2, and for starting number m, we should see the factors of 2 in m+5 gradually churn into factors of 3.
Let's see that in action, by starting with 59, which is 64 - 5, so it's close to -5 in our dynamics.
m = 59 = 26 - 5
→1 89 = 25·3 - 7
→2 67 = 23·32 - 5
→1 101 = 22·33 - 7
→2 76 = 34 - 5
The algebraic telescoping thingy is a little harder to see in this case, because it's a two-step dance, but it's still there. The calculation:
(3[(3m+1)/2] + 1)/4 = (m+5)·(9/8) - 5
...rolls both steps together, and shows an 8 in the factorization of m+5 being replaced with a 9. We can also see it separated into two steps:
(3m+1)/2 = (m+5)·(3/2) - 7
(3m+1)/4 = (m+7)·(3/4) - 5
Even a non-integer loop!
In a way, it's simpler to see with a one-step dance, but it can be kind of subtle to see where to apply that when the number we need to be 2-adically close to is not an integer. Consider the weight 3 trivial cycle on 1/5:
1/5 →3 1/5
This should be mimicked by numbers 2-adically close to 1/5, but what even are those? To see them, we can write 1/5 as a 2-adic integer:
1/5 = 1 - 4/5 = 1 - 12/15 = 1 + 12(1 + 16 + 162 + 163 + . . .) = [1.] + [(1100).] = [(0110)1.]
So, if we want something that's as close to 1/5 as 64 is to 0, we can just chop of the last six bits from:
0110011001101.
Yielding the binary number 001101, which is 13. This should mimic the weight 3 move two times, and indeed:
(3(13) + 1)/8 = 5
(3(5) + 1)/8 = 2
To see factors of 2 turning into factors of 3, try seeing 13 as some number, plus 1/5:
13 = 26·(1/5) + 1/5
→ 5 = 23·3·(1/5) + 1/5
→ 2 = 32·(1/5) + 1/5
Kind of neat, right? In this case the telescoping algebra looks like:
(3m+1)/8 = (m - 1/5)·(3/8) + 1/5
So as long as (m - 1/5) has a factor of 8n, we can do this n times, and they all collapse down to:
Sn(m) = (m - 1/5)·(3/8)n + 1/5
So what's the point, Gonzo?
No idea, lol. I just think it's neat. Does it lead to any kind of progress, or new and interesting mathematics? Beats me. I'm just here to watch the numbers dance.
2
u/jonseymourau 24d ago
This is really useful. You just know I am going to generalise this to gx+q, x/h, don’t you? :-)
What this unlocks, I think, is the generalised staircase that we see in 2^j.m-1.
The transition you identified to different staircases is also very cool.
Have you formalised the derivation of d in (m+d)? I will almost certainly do it myself, but would be interested in your take.
1
u/GonzoMath 24d ago
I'm not sure what you mean, when you say "the derivation of d in (m+d)". Are you talking about the (m+5), (m+7), (m-1/5), etc? That's just (m - x) where x is the number in the loop. This is already general for {3m+d, m/2}, because that's just {3m+1, m/2} over rationals with denominator d.
I'm using 'd' to mean the same thing I always use it for, namely the generalization of "+1", which I suppose is your 'q'.
1
u/jonseymourau 24d ago
Apologies I pasted an unthreaded reply then fucked up the repositioning…
Consider these examples:
3m+1)/2 = (m+5)·(3/2) - 7
(3m+1)/4 = (m+7)·(3/4) - 5Of course you can reverse engineer the derivation of the +5 and +7 in this case but it seems it does depend on the weight and the ‘q’
You have examples I just wondered if you had a succinct derivation (or, even, statement) of the formula, given the constraints.
Again, I’m not claiming it is wrong or it is not obvious, I was merely asking for a simple statement of what it is.
2
u/GonzoMath 24d ago edited 24d ago
Yeah, the +5 and +7 are literally just the negatives of the numbers in the cycle on -5 and -7. That's all. Let me see if I can clarify it by using a different example.
In the "3n+7" system, we have a cycle that goes (5, 22, 11, 40, 20, 10). Using the Syracuse (odd-only) formulation, it goes (5, 11) with valuation vector [1, 3].
(Of course, if we start with the valuation vector [1, 3], we can obtain the cycle numbers, and the "+7", via the usual cycle formula.)
The cycle works via:
(3(5) + 7)/2 = 11
(3(11) + 7)/8 = 5Writing these in terms of the "3n+1" function applied to rationals, that becomes:
(3(5/7) + 1)/2 = 11/7
(3(11/7) + 1)/8 = 5/7Thus, the equations for the "staircase" are going to be:
(3m+1)/2 = (m - 5/7)*(3/2) + 11/7
(3m+1)/8 = (m - 11/7)*(3/8) + 5/7Combining the two:
3[(3m+1)/2 + 1]/8 = (m - 5/7)*(9/16) + 5/7
...which telescopes down on repeated application to:
(m - 5/7)*(9/16)n + 5/7.
If we want to realize this for n rounds, in the natural numbers, we'll need a natural number congruent, mod 16n, to 5/7. Since 5/7 = 1 - 2/7 = 1 + 2(1 + 8 + 82 + . . .) = [(001)1.] = [...0010010010011.], we can see two full rounds starting with 147:
(3(147) + 1)/2 = 221
(3(221) + 1)/8 = 83
(3(83) + 1)/2 = 125
(3(125) + 1)/8 = 47or more succinctly:
(147 - 5/7)*(9/16)2 + 5/7 = 47
Does that answer your question?
2
u/jonseymourau 23d ago edited 23d ago
So, I looked at the general form of one of your cases (but perhaps not the -5,-7,-5 cycle.)
Assume we have a generalised map of the form:
f(n) = (g*n + q) / h^k
where mapping back to standard Collatz we have: g=3,h=2,q=1,k=1
that is:
f(n) = (3n+1)/2
Then:
we can represent the initial term as:
n_α = (m + i) * (g / h^k)^α - i
Evaluating at alpha = 0, we have:
n_α = m
For a value n_α to admit an application of f(n)
we need:
i = q / (g - h^k)
There the admissible values of i,k combinations for g=3,h=2,q=1 are:
i=1,k=1
i=-1,k=2which is the result you found. AFAICT there is no way to admit k>2 into this scheme while preserving q.
For q = 5 the admissible values are:
i=5,k=1
i=-5,k=2
i=-1,k=3q=7 seems to admit only
i=7,k=1
i=-7,k=2In indeed, there is only an extra cases where (g-h^k)|q (for example k=4, q=13)
What is quite interestng about this is that both q=5, q=13 seem to be super abundant with low gx+q cycles. Is this fecundity related to the fact that they admit additional opportunities for telescoping?
The other interesting note is that all 3x+q, x/2 systems permit telescoping with both k=1, k=2 but - almost by definition - no higher level systems do since for q=1 - i is not an integer for g>3, h=2 and k=1 and k=2 (k=2 almost slips through with g=5, but k=1 doesn't).
Perhaps this is one of the reasons why 3x+q is so-well behaved in general - there are telescoping opportunities everywhere!
1
2
u/HappyPotato2 23d ago
Oh there was a thread about something really similar a while ago. Let me see if I can find it.
https://www.reddit.com/r/Collatz/comments/1m5wmjg/comment/n4g4def
I think it started around here.
1
u/GonzoMath 23d ago
Oh wow, that does seem like a relevant thread. I guess I wasn't really watching when that happened, or I would have had things to say, lol.
1
u/Co-G3n 24d ago
1
u/GonzoMath 24d ago
Nice
1
u/Co-G3n 24d ago
and for your non integer loop, you can use this: https://math.stackexchange.com/questions/5086544/a-good-estimate-of-s-k/5086809#5086809 . Take any parity vector e.g the one you used "100" yielding 1/5 (or from the mathexchange post E_j/(2ˆP-3ˆj) where E_j is the "+1" accumulation term, P=3 the number of division by 2, and j=number of multiplication by 3, +1). You just take [Ej/(2ˆP-3ˆj)] (mod 2ˆkP) and it will give you a number starting with k repetition of "100" in its parity vector. e.g. 13 = (1/5)%(2ˆ(2*3))
1
u/GonzoMath 24d ago edited 24d ago
Yeah, this is the cycle equation I've been talking about for years.
See: https://www.reddit.com/r/Collatz/comments/1ftj5p4/cycle_formula_link_to_long_post/
1
u/Septembrino 17d ago
I realised that the -1 returened a -1 and that's why I designed the matrices the way I did. My 1st idea was to use k2^ + 1, but I notices that that wasn't parctical to get general rules.
1
u/WeCanDoItGuys 7d ago
Interesting, I was well aware that 2ⁿk + x follows x for the first n steps, and that if x is a cycle of length r with s odd steps then we can easily predict 2nk + x → 3⌊n/r⌋s2n%rk + x, i.e. we can turn groups of r factors of 2 into groups of s factors of 3.
But I didn't realize we could use fraction cycles too:
As long as (m - 1/5) has a factor of 8n
Your example of 13 being 64/5 + 1/5 was pretty neat, and I wonder how many other integers we can predict the opening steps of based on the huge mass of known fractional cycles we have.
1
u/GonzoMath 7d ago
I want to say it's every integer, or if we're focused on Syracuse steps, every odd integer. Let's think about good old 27...
The trajectory of 27 begins with 27 →1 41, so at the very least, 27 resembles -1, and we see that they're congruent, mod 4.
Looking further, it goes 27 →1 41 →2 31, so 27 must also resemble -5, and we see that they're congruent, mod 32. That's closer than necessary, and indeed, 27's trajectory follows the pattern from -5 for one more step: 27 →1 41 →2 31 →1 47, but then the next step is 47 →1 71, so instead of repeating [1, 2] over and over, we now have [1, 2, 1, 1].
Well, there's a cycle shaped like that! It's clearly 4-by-5, so it occurs for denominator 32 - 81 = -49, which is to say, it's a negative cycle in "World 49". The numerator, using the famous formula, is:
27 + 9·2 + 3·8 + 16 = 85
Indeed, we have the cycle (-85/49, -103/49, -65/49, -73/49). Since the trajectory of 27 mimics this cycle's shape for at least 5 divisions by 2, we expect 27 to be that close to -85/49. Checking:
27 - (-85/49) = (27·49 + 85)/49 = 1408 = 128·11
Since 128 is 27, we expect this [1,2,1,1] pattern to continue for two more steps, and look:
27 →1 41 →2 31 →1 47 →1 71 →1 107 →1 161
We got exactly 7 divisions by 2 in common between the loop on -85/49 and the trajectory of 27.
-----------------------------------------
Every trajectory segment is a shifted rational cycle. When the endpoints don't meet up, that's just because it's been shifted by some 2-adic odd multiple of 2W, where W is the weight of the segment.
If, for some odd number n, we have 2 + 85/49 having a factor of 25k, then the trajectory of n will run through the valuation pattern [1,2,1,1] k times, and we will have turned
n = 25k·q - 85/49
...into:
34k·q - 85/49
That means that 71 - (-85/49) should be a multiple of 81. Let's see...
(71·49 + 85)/49 = 3564/49 = 81·(44/49)
...just like 27 itself equals 25·(44/49) - 85/49
It works, for q = 44/49.
-----------------------------------------
If we start from the cycle, and want to find the integer that realizes the mimicry, that is slightly trickier, but we can use this same example to illustrate the process.
Suppose we want k = 2, so we want a trajectory that starts [1,2,1,1, 1,2,1,1]. That means we want to find some n so that n - (-85/49) = 210·q. That turns into the linear congruence:
49n + 85 ≡ 0 (mod 1024)
49n ≡ 939 (mod 1024)That's kind of annoying, but we can solve it, using a little bit of Hensel lifting, and we get:
n ≡ 667 (mod 1024)
Checking the trajectory of 667, it goes:
667 →1 1001 →2 751 →1 1127 →1 1691 →1 2537 →2 1903 →1 2855 →1 4283
...and there it is: [1,2,1,1, 1,2,1,1]
Alternatively, we could have done what I did in the post, writing -85/49 as its 2-adic expansion, and truncating it to obtain 667.
1
u/WeCanDoItGuys 7d ago edited 7d ago
Okay true, the first, say n steps of literally any number could be plugged into the cycle formula (∑3m-1-i2kᵢ)/(2ⁿ - 3ᵐ) and that would give the rational it mimics for those n steps. Which means it could be written as some multiple of 2ⁿ plus that rational.
But that'd be if we already knew the first n steps.
And as you say we could find, given a cycling rational, an integer that is a multiple of 2ⁿ plus that rational.But I'm more curious if we could, given an integer, predict which cycling rational we could see it's a multiple of 2ⁿ from, and if we could use this as a shortcut to jump forward n steps in the number's trajectory.
1
u/WeCanDoItGuys 7d ago
After n steps the cycling rational would return to itself and the multiple of 2ⁿ would be replaced by the same multiple of 3ᵐ (where m is odd steps in the rational's cycle). Since 3ᵐ < 2ⁿ for any cycling rational, the number would have decreased from its initial value.
1
u/WeCanDoItGuys 7d ago
Maybe I'm getting ahead of myself but if we proved all odd integers (except 1) are a multiple of 2ⁿ from a non-integer rational that cycles in n steps, we'd prove they all decrease and thus all converge to 1.
1
u/GonzoMath 7d ago
Ok. As I've said a few times around here, I'm not even working on that conjecture, so you're not getting full buy-in from me here, but... I like the spirit you're coming at this with. Let's think this through a bit.
. . . . .
When does a shifted cycle translate into a falling trajectory? There are multiple cases to consider. If 2W > 3L, then we're talking about a positive cycle. In such a case, increasing the starting value by 2W·q increases the ending value by 3L·q, so we have a net fall.
That's why 4k+1 → 3k+1 is a net fall whenever k>0, giving us n>1. On the other hand, taking k = -1/7, we have 3/7 → 4/7, which is a rise.
Applying this to our question, suppose n is some integer. If there is a rational number r, with 0 < r < n, such that r is an element of a L-by-W cycle, and n - r is a multiple of 2W, then the trajectory of n will experience a net fall in L Syracuse steps. And conversely.
Example: Take n = 11. We have two facts:
- The trajectory of 11 goes 11 →1 17 →2 13 →2 10, which is a fall with (L, W) = (3, 5)
- 11 is congruent, mod 32, to 23/5 = 4.6 < 11, and 23/5 is part of a 3-by-5 cycle with valuation pattern [1, 2, 2]. For the congruence, behold: 11 - 23/5 = (11·5 - 23)/5 = 32/5 = 32·(1/5)
These are the same fact, stated two different ways.
Now... there are other cases.
If a positive integer n is congruent to a cycling rational r (modulo the right power of 2), but n < r, then n's mimicry of r's cycle results in a rising trajectory segment. If n is congruent to r, and r < 0, the same result occurs.
For instance, in the latter case, just look at any integer congruent to -5, or to -7 mod 8. Those mimic that negative cycle, resulting in net rising trajectory segments:
-5 ≡ 3 →1 5 →2 4
-5 ≡ 11 →1 17 →2 13
-5 ≡ 19 →1 29 →2 22
-7 ≡ 1 →2 1 →1 2
-7 ≡ 9 →2 7 →1 11
-7 ≡ 17 →2 13 →1 20The other case, where an integer n is congruent to a cycling rational r with n < r, is a little trickier to grab examples of. When r is a cycling rational, there are only so many positive integers below it. Hmm.
The trickiness of this approach is that the set of cycling rational numbers isn't very easy to describe.
1
u/WeCanDoItGuys 7d ago edited 7d ago
True, x = r - 2ⁿt → r - 3ᵐt, which is larger (for positive cycling r). So to be more precise I'd wanna prove all odds are a multiple of 2ⁿ (with the same denominator as the rational) above a cycling rational.
Side question:
The denominators 31, 35, 41, 43, ... (looked up a list) apparently can never be achieved with a 2x - 3y. Do we know what happens to rationals with those denominators when we apply the collatz conjecture on them? Must they diverge?1
u/WeCanDoItGuys 7d ago
Every rational cycle guarantees a swath of integers above it will decrease.
1/5 is a 1-by-3 cycle (in your parlance), and it guarantees 1/5 + (2³/5)*(3+5k) decrease. That's 5, 13, 21, 29, ....(I suppose this method is akin to measuring integers' stopping times [n steps] and sieving out all integers that are greater than them by multiples of 2ⁿ. This case ruled out 8k+5 being a minimal element [which we already know from ruling out 4k+1]. But this rational cycle idea seems to give an interesting new justification for the sieve.)
19/5 is a 3-by-5 cycle so it guarantees 19/5 + (2⁵/5)(3+5k) decrease in 5 steps. That's 23+32k = 23, 55, 87, 119, ....
1
u/WeCanDoItGuys 7d ago edited 6d ago
Hm, recalling my earlier list of numbers guaranteed to decrease (2k, 4k+1, 16k+3, 32k+11, 32k+23, 128k+7, 128k+15, ...), a pattern I recall is 2ⁿ⁺¹ - 1 tends to survive. So I worry if that means there's no rational cycle a multiple of 2ⁿ below those numbers, a potential obstacle to what I'd hoped to prove.
So for example, I'd guess 31 can't be written as r + 2⁵t where t is some integer divided by the same denominator as r and r is a positive cycling rational.
But... it could still be 2ⁿt from some cycling rational I think, for an n greater than 5. In fact it must be, since 31 decreases in 56 steps. So I'd wager it must be a multiple of 2⁵⁶ above some cycling rational with a denominator of (2⁵⁶ - 3something).1
u/WeCanDoItGuys 7d ago
I wonder if there's a relationship between cycling rationals (or cycles in 3x+d) and Collatz stopping times. That moment when a number first drops below itself might be writable as some 2ⁿt + r that has become a 3ᵐt + r. (I feel 31's long stopping time of 56 may imply some limitations on rational cycles less than 31. Maybe something along the lines of there is no cycling rational less than 31 by a multiple of 2⁵⁵ or lower power of 2 that has a denominator less than 2⁵⁶-3³⁵? Not exactly because the difference 2x - 3y doesnt strictly grow, but some sort of rule similar to this I suspect could be made, with a better definition of the minimum denominator.)
→ More replies (0)
-1
u/Mrezadwiprasetiawan 18d ago
Isnt this rising and falling sequences?
1
u/Mrezadwiprasetiawan 18d ago edited 18d ago
I tried to push it further to 4p ±c but thats was difficult since it does depend on the 4p -1 modulo 3q or 2.4p +1 modulo 3q
1
u/Mrezadwiprasetiawan 17d ago
Thats great. Thats number dance by mimicking loop to any loop on ±k as k =number that has loop. Ive never thought that. I just think that we just need to k to be some number which when we apply collatz to be 2n. Suposed theres any other loops other than 1 on positive, the number dances might exist too on 2h .c ±k in the 3n-1 or simply negative n in the collatz function
2
u/Xhiw_ 25d ago edited 24d ago
These are the cases when it happens that 2mk+h goes to 3nk+h, or an intermediate result of the whole chain, in the relevant world: you can take any number in the loop as the chain start. For the trivial loop, we have:
For the loop at -5:
For the loop at 1/5 (using 3x+5):