This post turned out to be too long and image-dependent to be stable on Reddit, so I've moved its contents to a Google Doc.

Link: Practical Continued Fractions for Collatz

Many of us have independently discovered that a minimal counterexample to the Collatz conjecture would have to satisfy an increasingly stringent set of conditions, when we consider residue classes modulo 2^(k), for increasing values of k, because a larger and larger fraction of classes can be shown to "descend".

Just for example, we know that anything of the form 4k+1 "descends" to 3k+1 very quickly. Indeed, as long as k > 0. It's true that 4k+1 > 3k+1.

This kind of argument "lifts" to higher powers of 2, so for example, by the time we get to k=4, so we're looking through mod 16 lenses, the only remaining congruence classes are 7, 11, and 15. All of the others "descend". By the time we get to k=10, so we're looking through mod 1024 lenses, there are only 64 classes that aren't shown to "descend".

I saw another post about this kind of thing, and started thinking about how there are infinitely many non-descending trajectories under the Collatz map, when we apply it to rational numbers that are also 2-adic integers, i.e., rational numbers with odd denominators. Such numbers are in congruence classes mod 4, 8, 16, 32, etc., so... how does that work? Does every minimal cycle element over the rational numbers belong to classes that pass the sieves at every level?

Immediately, the thing to do seems to be to check some examples. Like, what about 19/5? It's a cycle min, so its trajectory never descends. Let's look at its 2-adic expansion:

19/5 = ....1100110011001100110111.

That four digit pattern keeps repeating to the left, and we could shorten it, using parentheses to indicate repetition, as:

19/5 = (0110)111.

Anyway, this makes its residues clear, modulo every power of 2:

19/5

≡ 1 (mod 2)
≡ 3 (mod 4)
≡ 7 (mod 8)
≡ 7 (mod 16)
≡ 23 (mod 32)

and so on. I stopped at 32 just now because that's where we have a question arise. When we test the expression 32k + 23, it seems to descend!

32k + 23
96k + 70
48k + 35
144k + 106
72k + 53
216k + 160
108k + 80
54k + 40
27k + 20

However, the number 19/5, despite being congruent to 23 (mod 32), doesn't descend! So what gives?

Let's consider the claim that the above chain is a "descent", anyway. Let n = 32k + 23, and let's compute:

32k + 23 > 27k + 20
↔ 5k > -3
↔ k > -3/5
↔ n > 32(-3/5) + 23 = (-96 + 115)/5 = 19/5

Well, how about that? If n ≡ 23 (mod 32) AND n > 19/5, then n's trajectory has to descend.

(Yes, in a way we just used the argument that 32k+23 descends as an alternative way to discover that there's a rational cycle with min element 19/5. Pretty cool, huh?)

What's your point, Gonzo?

Fair question, and I'm not sure what to do with this. What I'm saying though, with this post, is that there's a bit more going on, with these descent arguments, than we might think about at first. Each descent argument of this style looks like this:

(2^(W))k + a
...
...
...
(3^(L))k + b

where 3^(L) < 2^(W) and b < a.

(Exception for 4k+1 descending to 3k+1, in which case a = b, but we know that corresponds to descending as long as k > 0, which puts our starting number > 1.)

In fact, if we do our sieving properly, then 3^(L) is always the largest power of 3 smaller than 2^(W), or we would have caught this case for a smaller W.

So, if we now analyze the claim that this is a descent, we should obtain a condition on how large the original number has to be for that to be true:

n = (2^(W))k + a > (3^(L))k + b
↔ (2^(W) - 3^(L))k > b - a
↔ k > (b - a) / (2^(W) - 3^(L))
↔ n > (2^(W))(b - a)/(2^(W) - 3^(L)) + a = ((2^(W))b - (2^(W))a + (2^(W))a - (3^(L))a) / (2^(W) - 3^(L))
↔ n > ((2^(W))b - (3^(L))a) / (2^(W) - 3^(L))

That number there – ((2^(W))b - (3^(L))a) / (2^(W) - 3^(L)) – is the threshold where the descent argument kicks in.

Hello. I have posted before about 2-adic numbers, and I think I made the same mistake that a lot of teachers and textbook authors do. I approached it in a manner that was too... theory-forward.

For an amateur Collatz researcher, the thing about 2-adic numbers is, "Why do I care?" This post is an attempt to answer that question.

One cool thing about the Collatz map is how it acts in such a tidy way on numbers written in binary. If the binary rep ends in a zero, drop it! If it ends in a 1, do this other thing! So simple.

What's wild and exciting is that it works exactly the same way on negative numbers and some rational numbers; we just have to be able to write them so they look like natural numbers in binary.

Here's where 2-adic numbers come to the rescue. The 2-adic representation of a number simply answers the question: If this number had an ordinary binary representation, like a natural number does, what would it be?

2-adics let us write negative and rational numbers AS natural numbers in binary, in a consistent way!

The only rule is: The arithmetic has to work!

Thus, we can represent -1 as a natural number in binary, as long as it plays the game right. When we add 1 to it, we'd better get 0!

This can always be done, as long as we relax the restriction that a "natural number" has to have a finite number of digits. As it turns out, that relaxation gives us just the wiggle room we need to write -1 as

-1 = ...1111111.

So it's like 1, but more like 11 (3), but more like 111 (7), but... all the way. If you add 1 to it – and remember, we're in binary – you get 0 in the units spot, and you carry a 1. Then you get another 0, and carry a 1. Then you get another 0, and carry a 1...

Everything we write down on bottom is 0, and that carried 1 just gets carried off into the sunset, and we don't have to worry about it.

What about a fraction? What about like... 1/3? How do we write that?

It's easier to write -1/3, honestly. Then, working out regular 1/3 from there is easy.

What's up with -1/3? Well, that's the number with the property that three-times-it is negative 1. So here's a good binary arithmetic problem for you. By hand, multiply

.....0101010101.

by 3, which we write as "11".

That multiplication has the effect of replacing every "01" block in the above number with a "11" block, thus turning the whole unwieldy thing into:

.....1111111111. = -1

So we've found -1/3. To get the positive version, it appears all we have to do is add 1:

.....0101010110. = 2/3

and then divide by 2:

.....010101011. = 1/3

Under the 2-adic perspective, numbers such as -1 and 1/3 are no different from natural numbers! Most of what we say about Collatz is blind to how *long* a number happens to be; we tend to be focused on the digits near the right end.

Therefore, anything that you prove follows from the Collatz rules, unless it explicitly uses the finiteness of the binary representation, had better also be true for negatives, rationals, and possibly non-rational 2-adic integers.

...000000001. = 1
...111111111. = -1
...010101011. = 1/3

These are all perfectly good inputs to the Collatz map!

I've been making a few of these recently, and this is one of my favorites. I posted some version of it a couple of years ago, but this is way better, and I'd be happier to hang it on my wall:

Basins of attraction for \"3n+23\", odd inputs

I feel like I'm at a beach-side resort on another planet. But I digress. Unless that's actually related to the picture somehow... hmm.

The idea is that every number is plugged into the "3n+23" map, and the trajectory run until it reaches one of the eleven available cycles. That color-codes the seed value, and we're basically just looking at odd numbers from... some lower bound to some upper bound.

Like, for example, a row right near the middle has seeds -21, -19, -17, . . . 17, 19, 21, and then the row above it is like 25, 27, 29, . . . 63, 65, 67, and then etc.

Anyway. Just thought you might dig the pic.

I've posted numerous times talking about the Syracuse acceleration of the Collatz map:

For n odd: S(n) = (3n+1)/2^(v)

where 'v' is chosen so that the output is again an odd integer. When you do this, a trajectory itself, just n_0, n_1, n_2, etc., doesn't tell the full story, because you also need to know the value of 'v' at each step. Of course, that can be reconstructed from the odd numbers themselves, and it can be presented alongside the main trajectory, to let us know how much division happens between each pair of multiplications:

Trajectory: (7, 11, 17, 13, 5, 1)
Shape vector: [1, 1, 2, 3, 4]

• (3(7)+1)/2**^(1)** = 11
• (3(11)+1)/2**^(1)** = 17
• (3(17)+1)/2**^(2)** = 13
• (3(13)+1)/2**^(3)** = 5
• (3(5)+1)/2**^(4)** = 1

In general, for positive integers, an entry of 1 in a trajectory shape vector will correspond to a rise in the trajectory, and an entry greater than 1 will result in a fall.

This is all great, but I want to talk about a corresponding idea for Steiner trajectories.

What is a Steiner trajectory?

A previous post about Collatz shortcuts, including the Terras, Syracuse, and Steiner maps.

I don't know how widely used this terminology is, but it seems to make sense. Steiner defined a "circuit" in his '77 paper, as any number of Syracuse steps with v=1, followed by a single Syracuse step with v > 1.

In other words, it collapses a few v's from our Syracuse thinking into one, while shortening the trajectory.

To be clear, we're just taking the trajectory one circuit at a time, so in the example above, instead of 7, 11, 17, 13, we go straight from 7 to 13. After that, 13 to 5 is a single circuit by itself, and so is 5 to 1.

With all this compression, even more auxiliary information is needed to flesh out the full shape, so first let's write down our formula concretely, and name some variables.

Warning: the Syracuse 'v' and the Steiner 'v' are not the same thing. I thought about using different letters, but... they're both 2-adic valuations, and I didn't want to unnecessarily proliferate notation.

For odd n: R(n) = ((n+1)(3/2)^(v) - 1)/2^(k)

where we now have two parameters, v and k. In each case, they're chosen so that we divide by 2 as many times as possible, landing on another odd number.

First, 'v' is the number of 2's we can divide out of (n+1), and then 'k' is the number of 2's we can divide out of ((n+1)(3/2)^(v) - 1).

Going back to the circuit from 7 to 13, recall:

• (3(7)+1)/2**^(1)** = 11
• (3(11)+1)/2**^(1)** = 17
• (3(17)+1)/2**^(2)** = 13

The parameter 'v' counts how many Syracuse steps this is, and the parameter 'k' counts how much the final exponent is greater than 1. So, in this case, we'd have (v, k) = (3, 1). That's the shape of this circuit.

For any circuit, we'll have both parameters positive integers; you don't get zeros doing it this way. In a way, we can read the circuit shape of (3, 1) as meaning three rises (7 to 11, 11 to 17, 17 to 26) followed by a short fall (26 to 13).

In contrast, the circuit from 13 to 5 is very short:

• (3(13)+1)/2**^(3)** = 5

That's only one Syracuse step, so v=1, and the "final" exponent is 3, so k=2. The shape of this circuit is (1, 2): short rise, larger drop.

Full example

Here's the full Steiner trajectory from 27 to 1, along with its vector of circuit shapes, in the form of some computer output:

  World 1 Steiner trajectory:
      (27, 31, 121, 91, 103, 175,
       445, 167, 283, 319, 911,
       577, 433, 325, 61, 23,
       5, 1)

  The trajectory reaches the cycle minimum after 17 Steiner circuits.

  Trajectory shape vector:
      [(2, 1), (5, 1), (1, 1), (2, 1), (3, 1),
       (4, 1), (1, 2), (3, 1), (2, 1), (6, 2),
       (4, 3), (1, 1), (1, 1), (1, 3), (1, 2),
       (3, 4), (1, 3)]

You can see that the highest point in this version of the trajectory, 911, is reached via that (6,2) circuit, which is clearly a big rise, followed by a modest fall.

Why do we care?

Ha! In many cases, you probably don't, but what I find interesting here is how the Steiner map – just like the Syracuse map, the Terras map, the original Collatz map – provides its own unique window into exploring the dynamics of a trajectory (or cycle).

In particular, Steiner trajectories capture, through their circuit-shape vectors, a larger-scale sense of rising and falling than we get from Syracuse steps alone. Simply condensing the trajectory of 27 into something that short is kind of an accomplishment, and then being able to read its broad-grained textures...

It also gave me a cool idea. Since we have these (usually) small natural numbers, representing rises followed by drops... Why not interpret those numbers as musical intervals?

So now I've got a modest little module in my growing Collatz analysis software suite, where the user can choose a world and a seed, and then choose a key and a mode, and hear the Steiner trajectory as a little MIDI file. I just listened to 27, and it's pretty cool! Hard to dance to, but I gave it a little swing by delivering each rise-fall pair with a short-long, eighth-quarter, rhythm.

Will listening to trajectories with different properties do anything, for understanding or insight? I guess we never know until we try. Worst thing that might happen is I'll have some fun along the way.

I'd be happy to share the code, but it's kind of spread out over a few files, because it's this whole menu-driven program, and I'm trying to follow good software dev practices. However... hmm. What's the best way to share MIDI files on Reddit? This band totally takes requests!

Anything else?

All of that aside, I haven't used Steiner trajectories, or these little circuit-shape pairs, for any theoretical progress; I'm really just starting to play with them. This music idea seemed fun, and I got to learn a little more code.

The main point of this post is just to lay out a clear (I hope) exposition of one way of applying Steiner circuit analysis in a broader context than what Steiner talked about, and to provide (I hope) a nice, compact notation for describing them.

Thanks for reading!

In the "3n+d" variations, for any admissible choice of 'd', we get a Collatz-like dynamical system, which always seems to have finitely many cycles, with at least one in the positive domain. Some of these different "worlds" only have one cycle, like "3n+7". Others, such as "3n+1", have only one positive cycle, but multiple cycles on the negative side. Or other things can happen; they all seem like different little... worlds.

In each world, cycles can also be "natural", or "reducing". These terms make sense if you know about the cycle equation, which as we know, has the form:

n = S / (2^(W) - 3^(L)),

where 'n' is the starting number of a cycle, S is calculated based on the odd/even order of the cycle elements, and W and L count total even and odd steps in the cycle.

A natural cycle

Here's a fairly simple cycle, the only known one in World 7. The numbers in it are

(5, 22, 11, 40, 20, 10)

That's two odd numbers, 5 and 11, and four even numbers, so L=2 and W=4. The shape of the cycle... after 5, we only have one even, but after 11 we have three, so we can write [1, 3] as its "shape vector", which you can also think of identifying the powers of 2 to use in the "accelerated" division steps.

Feeding these values into the cycle equation, we discover that the starting value for the unique cycle, with shape vector [1, 3], is given by the fraction:

S/(2^(4) - 3^(2)) = S/(16 - 9) = S/7.

It turns out, if you write the vector two different ways, as [1, 3] and [3, 1] ('cause it's a cycle), then you can get S=5 or S=11, but either way, the denominator is 7. So 5/7, and 11/7.

The denominator of the fraction gives you the "world number", and the numerators give you the elements of that cycle in "3n+d".

(We show, with the same equation, that "3n+1" has a fractional cycle, starting with 5/7 or 11/7, and that's also a valid way of looking at it.)

Notice that the fractions 5/7 and 11/7 are in lowest terms. They can't be simplified, or "reduced" by dividing tops and bottoms by some common factor. That makes this a "natural cycle".

A reducing cycle

Let's start from a shape vector this time:

[1, 5]

Getting W and L from this is easy: L is the length of the shape vector, and W is its "weight", or sum. Thus here, L=2 and W=6, so we'll get fractions that look like

S/(2^(6) - 3^(2)) = S/(64 - 9) = S/55

Apparently, we're in World 55, right? The two values that we get for S after cycling the cycle are 5 and 35. So we're looking at the fractions 5/55 and 35/55.

You can find a cycle with shape [1, 5] in World 55, and it goes:

(5, 70, 35, 160, 80, 40, 20, 10)

All of those numbers are multiples of 5. (If one is, then they all are, with these things*.)

If we realize that these are all really "3n+1" cycles, on fractions, then we'd write it as:

(5/55, 70/55, 35/55, 160/55, 80/55, 40/55, 20/55, 10/55),

and applying "3n+1" to those is just like applying "3n+55" to just the numerators:

• 3(5/55) + 1 = 3(5)/55 + 55/55 = (3(5) + 55)/55

However, nobody writes that fraction as 5/55. We call it 1/11. We can reduce them all, and they all end up with 11 in the denominator. Reinterpreting those, where we consider the numerators as integers, and play in World 11, we get this "3n+11" cycle:

(1, 14, 7, 32, 16, 8, 4, 2)

Now, that's still 2-by-6, with shape [1, 5]. It is, for all intents and purposes, the same cycle, and if we want to avoid redundancy, we just make a rule that starting values have to be co-prime to the world number, and then you just get one copy of each cycle shape.

It's kind of like how, if you write fractions in lowest terms, then you don't get different ones equaling the same rational value.

Anyway, this cycle, in World 11, is a "reducing cycle".

Reduction "luckiness"

Considering other 2-by-6 cycles, the other possible shape is [2, 4]. (We can write down [3, 3], but that's just like writing [3], two times.) So, what's up with the [2, 4] cycle? Well, it doesn't reduce. Viewing the elements as fractions, they're

(7/55, 76/55, 38/55, 19/55, 112/55, 56/55, 28/55, 14/55)

So, there are two different 2-by-6 cycles.

• Shape [2, 4]: occurs naturally in World 55, with starting value 7
• Shape [1, 5]: reduces to World 11, where it has starting value 1

Now, I haven't said much about S. I'm going to offer a probabilistic model. First, we'll just consider one element of a cycle. (Pick the smallest one). Now fix a shape class, such as 2-by-6, and a modulus m. Let's assume: The smallest S, for each cycle, is a multiple of m... with probability 1/m.

In other words, when we take these two shapes [1, 5] and [2, 4], each one played in a lottery where they tried to draw a multiple of 5. The first cycle won, and the second cycle lost.

What was the probability that at least one of the two cycles was going to win, and reduce to World 11? This is a binomial calculation, but the easiest way to do it is

P = 1 - (4/5)^(2) = 9/25

So that measures, in this model, how unlikely it is that we're seeing a 2-by-6 cycle in World 11. I usually take the reciprocal of that number, and call 25/9 = 2.777... the cycle's "luckiness".

A natural cycle has a luckiness of 1, and a reducing cycle has luckiness greater than 1. When multiple cycles reduce in the same way, I actually calculate their luckiness together, so luckiness is really a function of world number and shape class, for example:

F(d, L, W) = F(11, 2, 6) = 2.777...

How lucky is it, to find even one 2-by-6 cycle in World 11? That's how lucky!

Does any of this mean anything?

I'm so glad you asked. My answer is: I don't know! Isn't it great? It's kind of cool to study, though, because it really does seem to act a little bit like luck. We don't see really lucky cycle families very often. However, it seems to take more luck to reduce from a very large world number to a very small one, just because the reduction ratio (the lottery chance) is so extreme. I think we also see more luck among really "high" cycles, in terms of "altitude" (defined as the harmonic mean of the odd elements of the fraction version).

Honestly, I haven't dug that much into this whole idea yet. I've got a program that calculates luckiness, so I can basically type in any valid world number under 2000, and find out how lucky its cycles are.

Here, World 29 is a great example. It has:

• The single 1-by-5 cycle occurs naturally here, because 32 - 3 = 29. Being natural, it's luckiness is just 1.
• Then we get a single 9-by-17 cycle. It would naturally occur in World 111,389, along with its 1429 siblings. That's like buying 1429 tickets to a lottery where the chance of winning is 1-in-3841. Hmm. Kind of lucky to win even once, and the value is just about 3.217.
• Next, there are two 41-by-65 cycles, with stunningly high altitudes, so we're talking about five-, six-digit numerators. Real "high cycles". They should occur naturally in World 420,491,770,248,316,829, so the chance of winning that lottery, and reducing all the way to World 29... dang. On the other hand, the total number of 41-by-65 cycles is also a lot. Around 3,500,000,000,000,000; I haven't got the exact value right now. That's still not so many tickets, considering the odds. The fact that we see two of them in World 29 has luckiness 11.25, which is wild. It's like rolling an 11.25-sided die and hitting your mark. Hmm.
• There's also a negative cycle in world 29, and it's an 8-by-12. Their natural world would be 2465, so the reduction ratio is 85, so it's a 1-in-85 chance of reducing. The number of tickets bought to the lottery is 40, so it's a bit surprising that even one of them wins. Luckiness = 2.652

Notes about calculating luckiness

As the numbers get big, this can actually be difficult to calculate.

That calculation I did above to arrive at 25/9, was easy, because the numbers were quite modestly sized. When you're talking about a 114-by-222 cycle, reducing from World 6739986666785194913961795704250911536955912161822068393763504961335 to World 371 (where it's the unique cycle), the individual numbers such as reduction ratio, and "number of tickets" get awkward.

Worse than that, what if a lot of cycles reduce together? World 499 contains 41 different 10-by-16 cycles. Their natural world number should be 6487, so the reduction ratio is 13. The total number of 10-by-16 cycles in the whole universe of worlds is 497...

So we have the probability question: We attempt an experiment with probability p=1/13, and we attempt it 497 times. What's the probability that at least 41 of those experiments will result in success?

Technically, that's a binomial problem, but you don't really want to use the binomial theorem to do it.

There are normal and Poisson approximations that work, but the respective domains where one approximation will be better than the other is a bit fussy, IIRC.