A Simple Linear Diophantine Equation That Encodes All ~~Trajectories~~ Cycles

General
1

We set M = 3, meaning we classify each value in the trajectory by its remainder modulo 3. This gives three residue classes: [0], [1], and [2].

There are six possible transitions, but we are only concerned with the following (we ignore seed values that are multiples of 3 in this analysis):

  • From [1] to [2] via (3n + 1)/2
  • From [1] to [2] via n/2
  • From [2] to [1] via n/2
  • From [2] to [2] via (3n + 1)/2

For example, we observe that any value in [1] will either increase by 3k + 1 or decrease by 3k + 2 (for some integer k) when moving to [2].

The full transition table is as follows:

[1] → [2] [1] → [2] [2] → [1] [2] → [2]
-2 +1 -1 +0
-5 +4 -4 +3
-8 +7 -7 +6
… … … …

For any value of d in the rule (3n + d)/2 such that d is congruent to 1 modulo 6. the transition table below remains the same (shared across all cases with some offsets).

To construct a Diophantine equation that encodes all trajectories we use a simple trick.

For instance, summing values from the first column [1] → [2] can be expressed as:

S = -2x - 3y

For example, (-2) + (-8) + (-20) = -2(3) - 3(8) = -30.

The last column does not require a second variable, so we only need seven variables in total.

Thus, the full linear Diophantine equation (for d congruent to 1 modulo 6) becomes:

-2 x_1 - 3 x_2 + x_3 + 3 x_4 - x_5 - 3 x_6 + 3 x_7 = 0

With the following constraints:

  • When x1 = 0, x2 also equals 0
  • When x3 = 0, x4 also equals 0
  • When x5 = 0, x6 also equals 0

Since we end up with the exact same equation for each value of d that is congruent to 1 mod 6, each solution V can represent a trajectory in one of the systems (or worlds). However, there are some solutions that are phantoms and do not represent any trajectory.

2

Interesting … what solution corresponds to the trajectory starting at 31 and ending at 1?

1 Like
3

It’s been a while since I touched any of these equations, so I made a little mistake (forgot what the solutions represent :man_facepalming:)…
the solutions to this Diophantine equation represent only cycles, not full trajectories.
My bad..

But in the special case where d = 1 only, the equation reduces to

-2 x_1 - 3 x_2 + x_3 + 3 x_4 - x_5 - 3 x_6 + 3 x_7 = -N + 1

whose solutions represent any trajectory. Here, N denotes the starting value (seed).

Then the solution that corresponds to the trajectory starting at 31 and ending at 1
is V = (8, 796, 12, 492, 20, 2574, 2876):

-2*(8) - 3*(796.0) + (12) + 3*(492.0) - (20) - 3*(2574.0) + 3*(2876.0) = -30.0

A detailed derivation of the solution vector V can be found in this Python Fiddle:

https://python-fiddle.com/saved/ef1f0a43-683a-4aa3-ae65-3037d7eaa41c?run=true

I hope it clarifies how the solution was obtained. Please let me know if any part needs further explanation.

1 Like
4

Is this property known?

Maybe this is already known/obvious, but I just noticed it…

In a cycle

E: sum of all even numbers (no repetitions)

O: sum of all odd numbers (no repetitions)

t: number of odd steps

using

(3n + d) / 2 for the odd step

n / 2 for the even step

Then:

E - O = d.t

example:

d = 17; a_0 = 23

orbit(23, 17) :: [23, 43, 73, 118, 59, 97, 154, 77, 124, 62, 31, 55, 91, 145, 226, 113, 178, 89, 142, 71, 115, 181, 280, 140, 70, 35, 61, 100, 50, 25, 46, 23]

E = 1690; O = 1384; t = 18

E - O = 306 = 17 * 18 = d.t

5

Yes (and I think it is in one of mathkook’s paper for the case d=1).
It’s really simple to show: In a cycle, \sum\limits_t(\frac{3o+d}{2})+\sum\limits_{k-t}(\frac{e}{2})=\sum\limits_t o+\sum\limits_{k-t} e
with o the odd elements of the cycle, and e the even elements
You do the math and find out that d\cdot t+\sum o=\sum e

1 Like
6

I just found his website, and I had no idea he was a Professor of CS — or that he owned this forum. I only knew him from his YouTube channel and assumed he was just a regular member.

Much respect, Professor.

8

Extending the E − O Relation

(from cycles only to full trajectories)

In a trajectory:

E: sum of all even numbers (no repetitions)

O: sum of all odd numbers (no repetitions)

t: number of odd steps

h: number of even steps

m: minimum number in the cycle reached by N

Using

(3n + d) / 2 for the odd step

n / 2 for the even step

Then:

E − O = d·t + 2(N − m)

Next:

Setting m = 1 and d = 1:

=> E − O = t + 2(N − 1)

Now consider the forward trajectory:

A → … → B → … → 1 → 2 → 1

where A and B are two consecutive odd numbers that appear in the sequence.

Let X represent the sum of all even numbers that appear between A and B in the trajectory.

Then X can be calculated using the derived formula:

X = 3A − 2B + 1

and

2^{v2(3A+1)-1} = (3A + 1) / 2B

Example:

5 → 8 → 4 → 2 → 1 → 2 → 1

X = 8 + 4 + 2 = 5·3 − 2·1 + 1 = 14

2^(4-1) = (3*5 + 1) / 2(1) = 16 / 2 = 8

9

Working out the 2^(v2(3A+1)-1) part makes it obvious now lol.
I think that at least shows that maybe I didn’t make any mistakes.

10

That’s easy to show: every even number between A and B is B times a power of 2, so the sum can be written as 2B(2^{v2(3A+1)-2}+2^{v2(3A+1)-3}+....+1)=2B(2^{v2(3A+1)-1}-1).
Just replace 2B2^{v2(3A+1)-1} by 3A+1

1 Like
11

I’m going to work on the sum of odds between each two consecutive evens next. Maybe we’ll get a simpler version of the sum.

12

Also, I should’ve mentioned this—my bad. When it’s a normal trajectory (not a cycle) once you reach the last element and it equals m, you exclude it from everything.

13

Let’s say that you have …→A → B_1 → B_2 →… → B_i →C→… where A and C are even numbers and B_1, B_2,…, B_i are i consecutive odds, then the sum of these odds is 2(C-B_1)-i

Can be found the same way as for even, knowing that if you write B_1=b2^i-1 then B_2=b2^{i-1}3-1, B_3=b2^{i-2}3^2-1, … C=b3^i-1 (with b odd)

1 Like
14

Thank you very much

We have B_1 = A / 2 so Y = (2C - A) - i

15

From the formula:

m = (d·t − (E − O)) / 2 + N

and using:

O_min = 1 + 3 + 5 + … + (2t−1) = t² → the smallest possible sum of t distinct odd integers

E_min = 2 + 4 + 6 + … + 2h = h(h + 1) → the smallest possible sum of h distinct even integers

From two inequalities (I am in a rush and will include the steps later), I was able to find that:

E − O ≥ 2T(t) − 2T(h) − t

where T(k) = k(k+1)/2 is the k-th triangular number formula.

How significant is this lower bound? @Collag3n
Are these types of analyses even worth the effort / pursuing lol?
I don’t even know what or why am I even doing lol

16

It is always worth, but O>t^2 gives -O<-t^2 and I don’t see how you got the inequality (inverted?)

1 Like
17

I think I made a mistake with the sign. It’s supposed to be a (+):

E + O \geq 2T(t) - 2T(h) - t

The two inequalities I used:

Setting d = 1:

m = \cfrac{t - (E - O) }{2} + N
\begin{equation} m \geq \cfrac{t - (E - O_{min}) }{2} + N \tag{1} \end{equation}
\begin{equation} m \leq \cfrac{t - (E_{min} - O) }{2} + N \tag{2} \end{equation}

Full steps:

E_{min} - O \leq E - O_{min}

h(h + 1) - O \leq E - t^2

E + O \geq h(h + 1) + t( t + 1) - t

E + O \geq 2T(t) - 2T(h) - t

Testing with a few examples, the LHS (E + O) gives only positive numbers and the RHS gives negative numbers, so the inequality holds but I think that also makes it useless, lol.

18

Why not E + O\geqslant E_{min}+O_{min} \geqslant 2T(t) + 2T(h) - t ? Bounds…we rarely see how useful they can be until it become obvious that they are…

1 Like
20

For a trajectory starting from N under the Antihydra function, this relation holds at every step:

S = E + O = 2(n_k - N) + t

We can find the next n_k using:

n_k = \cfrac{E + O - t + 2N}{2} = \cfrac{S - t + 2N}{2}

where E and O are the sums of all even and odd values visited, n_k is the current value, and t is the number of odd steps.

Example: starting from N=8

8 → 12 → 18 → 27 → 40

step 1: n_k=12, E=8, O=0, t=0
        8 + 0 = 2(12-8) + 0 = 8
step 2: n_k=18, E=20, O=0, t=0
        20 + 0 = 2(18-8) + 0 = 20
step 3: n_k=27, E=38, O=0, t=0
        38 + 0 = 2(27-8) + 0 = 38
step 4: n_k=40, E=38, O=27, t=1
        38 + 27 = 2(40-8) + 1 = 65

I’m not sure if it is useful, but I thought to share anyway.

21

The formula for the Collatz sequence is:

n_k = \cfrac{O + t - E + 2 \cdot n_0}{2}

Example:

n_0 = 20

n_1 = (0 + 0 - 20 + 2*20) / 2 = 20 / 2 = 10
n_2 = (0 + 0 - (20 + 10) + 2*20) / 2 = 10 / 2 = 5
n_3 = (5 + 1 - (20 + 10) + 2*20) / 2 = 16 / 2 = 8
n_4 = (5 + 1 - (20 + 10 + 8) + 2*20) / 2 = 8 / 2 = 4
n_5 = (5 + 1 - (20 + 10 + 8 + 4) + 2*20) / 2 = 4 / 2 = 2
n_6 = (5 + 1 - (20 + 10 + 8 + 4 + 2) + 2*20) / 2 = 2 / 2 = 1

n_6 = (n_2 + 1 - (n_0 + n_1 + n_3 + n_4 + n_5) + 2*n_0) / 2 = 1

n_6 = (X + x - Y + 2*n_0) / 2 = 1
n_7 = (X + 1 + x + 1 - Y + 2*n_0) / 2 = 2
n_8 = (X + 1 + x + 1 - (Y + 2) + 2*n_0) / 2 = 1
...