MrMineev

On the topic of the $3n + 1$ Conjecture

Daniel Mineev

1 The Collatz Conjecture

The Collatz Conjecture, also known as the $3n + 1$ Conjecture, is one of the unsolved problems in number theory. The setting of the problem is simple. Let’s define $Δf$ as

{ 3n+1 Δf (n ) = -2-- if n is odd, n2 if n is even.

(1)

The conjecture states that for any n, if you apply this function enough times, it will hit 1. In this paper, I will be calling this function the step function.

2 Redefining the Step Function

The previous definition of the step function is good. However, it is expressed partially mathematically. A person might use this function to fix such an issue.

1--(- 1)x h(x) = 2

(2)

This function is equal to 1 when x is odd and equal to 0 when the number is even. We can use such a function to define the step function.

Δf (x ) = x(2.5h(x)+ 0.5)+ h(x )
x x
Δf (x) = x(2.51---(--1)-+ 0.5)+ 1--(- 1)
2 2

(3)

This is a better formula. However, this isn’t defined for real numbers x because of $(- 1)x$ . We will devise a different formula to make one that works with real numbers. The formula should oscillate back and forth between two lines, the $y = 3x+ 1$ and the $y = x 2$ . We know that a function that oscillates between $a$ and $b$ is defined as

a(x)+-b(x) a(x)--b(x) f(x) = 2 + 2 ϕ(x)

(4)

Where $ϕ$ is any function oscillating between -1 and 1. Now, again, let’s redefine the step function.

x x
f(x) = 3x+-1+--2+ 3x-+-1--2 cos(ax + b)
2 2
f(x) = 3.5x-+-1+ 2.5x+-1 cos(ax +b)
2 2

Let’s pick a to be $π$ so that the frequency of the cos wave would be 1. Then

f(2) = 1
4+ 3 cos(ax+ b) = 1
cos(ax+ b) = - 1
cos(2π+ b) = - 1
-1
b = cos (- 1) = π

The final function looks like this.

3.5x+ 1 2.5x + 1
Δf (x) =------- + -------cos(πx+ π)
32.5x + 1 22.5x + 1
Δf (x ) =------- - -------cos(πx )
2 1
Δf (x) = 3.5x+-1---(2.5x+-1)cos(πx)-
2

(5)

(6)

(7)

Such a function is defined for all real numbers, not only for integers. A graph of such a function looks like the following.

--012-05000215000

The two lines here are blue and violet. They are the $y = 3x+ 1$ and the $x y = 2$ . The red curve is the step function using the formula (5). This formula will be used for the step function throughout the paper. What about defining the function using $sin$ ?

3.5x + 1 2.5x+ 1
Δf(x) = ---2---+ ---2--- sin(ax+ b)

As with $cos$ let us set the a to $π$ . Then let us calculate b.

f(2) = 1
3.5x + 1 2.5x +1
---2---+ ---2---sin(ax +b) = 1
4+ 3 sin(πx+ b) = 1

sin(2π+ b) = - 1
b = sin-1(- 1) = - π∕2

Then the final equation using $sin$ looks like the following.

Δf (x) = 3.5x+-1 + 2.5x-+-1sin(πx - π) 2 2 2

(8)

Another way to write the step function is the following.

Δf(x) = 1.75x+ (- 1.25x- 0.5)cos(πx)+ 0.5

(9)

3 Developing Theorems

First let’s define some basic lemmmas.

Lemma 1 $∀x ∈ ℕ : Δf (x) ∈ ℕ$

This follows right from the initial definition of the Collatz Conjecture.

Lemma 2 $∃x ∈ ℝ \ℤ : Δf (x ) ∈ ℕ$

This is also quite obvivous, such lemma comes from the function’s graph. An example of a number that saticfies the statement is $≈ 3.619$ . Consider the section of the step function graph from 0 to 0.2.

05000050000⋅.1.1.2⋅.1.1.2.21515500--22

Looking at this graph, notice the section where $Δf (x ) < x$ . Let’s define H as the following.

Def 1 $∀x ∈ ℝ ∧ x ≥ 0 ∧x ≤ H : Δf (x) < x$

Then we can state the following.

Lemma 3 $∀x ∈ ℝ ∧x ≥ 0∧ x ≤ H : Δf (Δf(...(x)...)) = 0$

We can even state something stronger than this.

Theorem 1 $∀x ∈ ℝ∧ x ≥ H : Δf (Δf (...(x)...)) ⁄= 0$

4 Similar Numbers

When dealing with paths developed by iteratively applying the step function, a simple idea comes to mind when considering the similarities: Call two numbers alike if the path until 1 of one number is contained within the second number’s path as a prefix. A related definition I will introduce is similarity; two numbers are considered similar if one number’s path is until a number less than itself is contained within the same kind of path of the second number as a prefix. I will denote the set of all similar numbers to $x$ as $SIM# (x )$ , and the set of all alike numbers to $x$ as $SIM (x )$ . Let us look at how to compute similar numbers; as an example, pick $x = 5$ then one must first calculate the path til a number less than 5 (denoted as $PA# (5)$ )

( ) 1 2 3 4 P A# (5) = 5 16 8 4

(10)

Let us now write down this path as a function by applying the exact same operations done to the numbers $5$ , but now with $x$ .

3x +1 PA#5 (x ) =------ 4

(11)

Then, the claim of the fundamental theorem is as follows:

SIM# (5) = {x ∈ ℤ | 3x + 1 ≡ 0 (mod 4)}

(12)

SIM# (5) = {x ∈ ℤ | 3x ≡ 3 (mod 4)}

(13)

SIM# (5) = {x ∈ ℤ | x ≡ 1 (mod 4)}

(14)

In other words, any $x$ for which $P A#5(x) ∈ ℕ$ is similar to $x$ . The only way for this statement to be untrue is that we have broken the rules somewhere.

Case 1) We somewhere divide by two an odd number.
Case 2) We 3x + 1 a even number.

In the first case, whatever comes next will never hit a hole number, so it won’t be registered as similar. In the second case, an even number when dividing by two, we will return to case 1. This empowers one to calculate similar numbers and their properties efficiently.

For any $x ∈ ℕ$ the set $SIM# (x)$ has the following form.

a b SIM# (x) = {x ∈ ℤ | 3x + c ≡ 0 (mod 2 )}

(15)

Thus, similar numbers are distributed in a very particular way throughout the natural numbers; the difference between any two consecutive similar numbers is a power of two. This allows us to introduce a concept such as the coefficient of similarity of two natural numbers (denoted as $CSIM# (x)$ , which is defined to be the logarithm base 2 of the constant difference between two consecutive similar numbers. Using the previous example, one can conclude that $CSIM# (5) = 2$ , because $4 = 22$ .

We can also make theorems about the $CSIM (x)$ . For example, it is trivial to realize that if $x ≁ y$ (meaning $x$ and $y$ are not similar), then.

∀n ∈ SIM (x) : ∀m ∈ SIM (y) : n ⁄= m

(16)

Consider $I$ and $J$ then there must be no $a$ and $b$ that the following is true.

I + a ⋅2CSIM(I) = J + b ⋅2CSIM (J)
CSIM (I) CSIM (J)
J - I = a⋅2 - b ⋅2
(2CSIM (I),2CSIM(J)) | J - I
2min(CSIM(I),CSIM(J)) | J - I

(17)

Meaning

∀I,J ∈ ℕ : 2min(CSIM (I),CSIM (J)) ∤ J - I

(18)

For example, let us take numbers 3 and 5. Because $3 ≁ 5$ we know that $min (CSIM (3),CSIM (5)) ≥ 2$ .

5 Analyzing Infinite Paths

Consider Collatz Conjecture false, then a number $M$ must exist such that the path is infinite. This is a bit hard to work with; we can replace this with an analogous statement that $M$ has an infinite path until a number less than itself; in other words, $M$ never goes lower. This can be easily achieved by introducing induction over the natural numbers or simply selecting the smallest counterexample. Here, I will try to consider some examples of infinite paths and prove their non-existence to understand better the nature of the paths of the counterexample numbers.

Let us consider an infinite path, where the operations applied to the number would interchange one after another. The goal here is to consider the value of $SIM# (x)$ as we add more and more operations; in a sense, I will analyze the behavior of $SIM# (X)$ in the limit of interactions of the step-function. I will denote by $In(x)$ the generated path after $n$ iterations.

SIM_#(I²(x)) = {x ∈ ℕ∣3x + 1 ≡ 0 (mod 2)}
SIM_#(I⁴(x)) = = {x ∈ ℕ∣9x + 5 ≡ 0 (mod 4)}
SIM_#(I⁶(x)) = ... = {x ∈ ℕ∣27x + 19 ≡ 0 (mod 8)}
SIM_#(I⁸(x)) = ... = {x ∈ ℕ∣81x + 65 ≡ 0 (mod 16)}

It is quite simple to prove and observe the general formula for such an equation.

SIM# (I2n(x)) = {x ∈ ℕ | 3nx+ 3n - 2n ≡ 0 (mod 2n)}

(19)

Due to $2n ≡ 0 (mod 2n)$ , one can simplify the equation even further.

SIM# (I2n(x)) = {x ∈ ℕ | 3n(x + 1) ≡ 0 (mod 2n)}

(20)

And then again, noticing the factor of $x + 1$ , we can substitute in $x := x + 1$ , thus the needed modular equality needed to be solved is the following.

3nx ≡ 0 (mod 2n)

(21)

Such equality can be easily solved; one must find multiples of $2n$ , such that they are divisible by $3n$ ; in other words,

x = k2n 3n

(22)

One can see that due to the fundamental theorem of arithmetic, $n k = 3 y$ , thus $n x = 2 y$ , where $y$ is any natural number. Going backward from here, back to the original equation, we are left with an exact equation describing $n SIM# (I (x))$ .

2n n SIM# (I (x)) = {2 x- 1 | x ∈ ℕ}

(23)

Let $X$ be the minimal value of the set $2n SIM# (I (x))$ , then as $n → ∞$ , we have $X → ∞$ , thus there exists no natural number, such that it has such infinite path.

MrMineev

On the topic of the $3n + 1$ Conjecture

1 The Collatz Conjecture

2 Redefining the Step Function

3 Developing Theorems

4 Similar Numbers

5 Analyzing Infinite Paths

§

💬 Comments

MrMineev

On the topic of the Conjecture

1 The Collatz Conjecture

2 Redefining the Step Function

3 Developing Theorems

4 Similar Numbers

5 Analyzing Infinite Paths

§

💬 Comments

On the topic of the $3n + 1$ Conjecture