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.

7

An attempt to better explain the linear Diophantine equation I shared

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
19

So far I’ve only tested a few numbers manually, so investigating both of them more deeply next would definitely make sense. I’ll report back with any findings, whether they turn out to be interesting and useful or not :smile: