Collatz conjecture

DURMAGAMBETOV A.A DURMAGAMBETOVA A.A

Department of Mathematics

Eurasian Natioanal University

Astana

KAZAKHSTAN

Abstract: This paper presents an analysis of the number of zeros in the binary representation of natural numbers.

The primary method of analysis involves the use of the concept of the fractional part of a number, which naturally

emerges in the determination of binary representation. This idea is grounded in the fundamental property of the

Riemann zeta function, constructed using the fractional part of a number. Understanding that the ratio between

the fractional and integer parts of a number, analogous to the Riemann zeta function, reflects the profound laws

of numbers becomes the key insight of this work. The findings suggest a new perspective on the interrelation

between elementary properties of numbers and more complex mathematical concepts, potentially opening new

directions in number theory and analysis.This analysis has allowed to understand that the Collatz sequence initially

tends towards a balanced symmetric arrangement of zeros and ones, and then it collapses, realizing the scenario

of the Collatz conjecture.

Keywords: Collatz conjecture,fractional , integer parts

Received: April 19, 2024. Revised: September 11, 2024. Accepted: October 13, 2024. Published: November 6, 2024.

1Introduction

We will use the following well-known fact: if, for

the members of the Collatz sequence, zeros predom-

inate in their binary representation, then these mem-

bers will lead to a decrease in the subsequent mem-

bers according to the Collatz rule. A striking example

is when the initial number in the Collatz sequence is

equal to 2n. Let’s write the solution of the equation

n= 2xin the form x={x}+[x]and note that the

smaller x, the more zeros in the corresponding binary

representation for n. Developing this idea, we come

to the following steps.

• Analysis of the binary representation of simple

cases of natural numbers.

• Creation of a process for decomposing an arbi-

trary natural number into powers of two.

• Analysis of the proximity of the process to binary

decomposition at the completion of decomposi-

tion at each stage.

• Calculation of the number of zeros in the binary

decomposition of a natural number.

• Estimation of the Collatz sequence members de-

pending on the number of ones in the binary de-

composition.

2 Problem Formulation

This document reveals a comprehensive solution to

the Collatz Conjecture, as first proposed in [1]. The

Collatz Conjecture, a well-known unsolved problem

in mathematics, questions whether iterative applica-

tion of two basic arithmetic operations can invariably

convert any positive integer into 1. It deals with in-

teger sequences generated by the following rule: if

a term is even, the subsequent term is half of it; if

odd, the next term is the previous term tripled plus

one. The conjecture posits that all such sequences cul-

minate in 1, regardless of the initial positive integer.

Named after mathematician Lothar Collatz, who in-

troduced the concept in 1937, this conjecture is also

known as the 3n + 1 problem, the Ulam conjecture,

Kakutani’s problem, the Thwaites conjecture, Hasse’s

algorithm, or the Syracuse problem. The sequence is

often termed the hailstone sequence due to its fluctu-

ating nature, resembling the movement of hailstones.

Paul Erdős and Jeffrey Lagarias have commented on

the complexity and mathematical depth of the Collatz

Conjecture, highlighting its challenging nature.

3 Results

Consider an operation applied to any positive integer:

• Divide it by two if it’s even.

• Triple it and add one if it’s odd.

A sequence is formed by continuously apply-

ing this operation, starting with any positive integer,

where each step’s result becomes the next input. The

Collatz Conjecture asserts that this sequence will al-

ways reach 1 Recent substantial advancements in ad-

dressing the Collatz problem have been documented

in works [2]. Now let’s move on to our research,

which we will conduct according to the announced

plan. For this, we will start with the following

PROOF

DOI: 10.37394/232020.2024.4.7

Durmagambetov A.A, Durmagambetova A.A

E-ISSN: 2732-9941

Volume 4, 2024

Theorem 1. Let

M∈N,

[αj]−[αj+1] = δj>0,

ϵ1<0.45,

|Fj(x)|<|x|,

αj= [αj] + ϵj,

ϵj<1,

σj= 1 −ϵj.

Then for δj= 1

σj= 2−1σj+1 1−σj+1 ln 2

2+Fj σ3

j+1

12 !,

(1)

and for δj>1

σj= 2−δjσj+1 + 1 −2−δj−2−2δj+1

ln 2−

σ2

j+1 ln 2

4+ 2−2δjRj ln22σ3

j+1

8!.(2)

Proof. Consider

M−M= 0 =

i=1

2[αi]+ 2αj+1 −"j−1

i=1

2[αi]+ 2αj#

= 2[αj]+ 2αj+1 −2αj

2αj= 2[αj]+ 2αj+1 = 2[αj]+ 2[αj+1 ]−[αj]+[αj]+ϵj+1 .

Then, we proceed to functional relations between σj

and σj+1:

2ϵj= 2−δj+ϵj+1 + 1

⇒21−σj= 2−δj+1−σj+1 + 1

⇒ln(21−σj) = ln 2−σjln 2 = ln(2−δj+1−σj+1 + 1).

Evaluating for δj= 1, we get:

ln(2−δj+1−σj+1 + 1)δj=1

ln(2−σj+1 + 1)

=ln 2 + ln 1−σj+1 ln 2

σ2

j+1 ln22

4+Fj σ3

j+1

12 !.(3)

Continuing the computations for δj>1, we obtain:

ln(2−δj+1−σj+1 + 1)

=ln 1+2−δj+1 −2−δj+1 σj+1 ln 2

2−δj+1Fjσ2

j+1 + 2−δj+1

= 2−δj−2−2δj+1−2−δjσj+1 ln 2

2+2−2δjFjσ2

j+1.

(4)

Thus, we obtain the final formulas.

Theorem 2. Let

M= 3n= 2[α]+{α}=

n∗

i=1

γi2i,

1− {α}>0.55, n∗=nln(3)

ln(2),(5)

then

γi=0

1≥n∗

Proof. Let

3n= 2α⇒α=n

ln 3/ ln 2⇒3n= 2[α]+{α}.

Using Theorem 1, we construct the sequence

ϵi, mi, ϵ1={α},

2ϵ1=

i−1

k=0

2[αk]−α1+ 2αi−α1.

Suppose the binary decomposition process, according

to formula (1), stops at the j-th step. It immediately

follows that the remaining terms of the decomposition

are zeros, and we immediately achieve the truth of the

Theorem’s statement. Therefore, we consider the case

when the generation of the decomposition according

to formula (1) does not stop, and j reaches n. This

means that all σj>0, j < n.

Let’s conduct a more detailed analysis of the num-

ber of zeros and ones in our binary representation. In-

troduce the following notation:

l- the number of zeros in the binary representation.

m- the number of ones in the binary representation.

n- the binary decomposition bit size, then

n=l+m.

δj= 1, αj= 0,

βj= (1 −ln 2σj+1

2)/2 + Fj σ2

j+1

12 !)!−1

PROOF

DOI: 10.37394/232020.2024.4.7

Durmagambetov A.A, Durmagambetova A.A

E-ISSN: 2732-9941

Volume 4, 2024

δj>1, αj=

−2δj1−2−δj−2−2δj+1

ln 2+ 2−δjRjln22σ3

j+1

2−2δj+1

ln 2, βj= 2δj(6)

To solve the following equations

σj+1 =αj+βjσj

we introduce the notation λm- the number of ones af-

ter the appearance of αm>0and before the next

appearance of zero in the binary decomposition and

γm=

m+λm−1

k=m

βk, αm+λm+1 >0

Consider the set λ1, λ2, ....λn, . by definition λ1≥1

Define:

m(λ∗, i) = inf

k{k|λk>1 + i}

m(λ∗, i) = inf

k{k|λk>1 + i}

if the set k satisfying the condition is not empty. Let’s

perform a series of transformations to understand the

next steps.

σn+1 =αn+β1γ1

α1

β1γ1

n−2

k=0

γn−kβn−k+

n−2

m=1

γn−mβn−m

αn−m

βn−mγn−m

m−1

k=0

βn−kγn−k+

σ1

n−1

k=0

βn−kγn−k(7)

σn+1 =αn+α1

β1γ1

n−1

k=0

βn−kγn−k+

n−2

m=1

αn−m

βn−mγn−m

k=0

βn−kγn−k

+σ1

n−1

k=0

βn−kγn−k(8)

With the consideration of the definition of m(λ∗, i),

in case of existence λi>1

σn+1 =αn+α1

β1γ1

n−1

k=0

βn−kγn−k+

m(λ∗,i)−1

m=1

αn−m

βn−mγn−m

k=0

βn−kγn−k+(9)

n−2

m=m(λ∗,i)

αn−m

βn−mγn−m

k=0

βn−kγn−k+σ1

n−1

k=0

βn−kγn−k

σn+1 =αn+

m(λ∗,i)−1

m=1

αn−m

βn−mγn−m

k=0

βn−kγn−k+

n−1

m=m(λ∗,i)

αn−m

βn−mγn−m

k=0

βn−kγn−k+σ1

n−1

k=0

βn−kγn−k

n−1

m=m(λ∗,i)

γn−m(λ∗,i)αn−m

βn−mγn−m

k=0

βn−kγn−k+

σ1γn−m(λ∗,i)

m(λ∗,i)−1

k=0

βn−kγn−k(10)

Introduce the notation

α∗=inf

δi

|αi|

βi

, α∗=sup

0≤i≤n

|αi|

βi

β∗=inf

0≤i≤n, δi=1 βi, β∗=sup

0≤i≤n, δi=1

βi

A(m) =

k=1,δj=1

ln2(βj)+

k=1,δj>1

ln2(βj) = A1(m) + A2(m)(11)

by definition αi, γi

1< α∗< α∗<1.3

2< β∗< β∗<2/(1 −ln 2/2)

Rewrite equation (6) using i, m(λ∗, i)and assum-

ing that we have only one zero

σ1≤σn

β∗i2A(n−1) −α∗

β∗i2A(n−1)

m=m(λ∗,i)

m=1

2A(m)+

σn

β∗i2A(n−1) −α∗

(β∗i2A(n−1)

m=n−1

m=m(λ∗,i)

2A(m)

σ1<21.3

βi

It follows that after zero there cannot be more than

three ones. Suppose that between two zeros there are

two ones, using Theorem 1 and denoting

x(k) = 2−σi+k, k ∈ {1,2,3,4,5}

PROOF

DOI: 10.37394/232020.2024.4.7

Durmagambetov A.A, Durmagambetova A.A

E-ISSN: 2732-9941

Volume 4, 2024

we get the system of equations

Ax =b(12)

where A, A−1, b are defined below.

A=





2−s0 0 0

0 2 −1 0 0

0 0 2 −1 0

0 0 0 2 −t

0 0 0 0 2







(13)

b=











(14)

s= 2−δi, t = 2−δi+3

A−1=





1/2 s/4 s/8 s/16 s∗t/32

0 1/2 1/4 1/8 t/16

0 0 1/2 1/4 t/8

0 0 0 1/2 t/4

0 0 0 0 1/2







(15)

Using Theorem 1 again

21−σi+4 = 2h1

2+t(t+ 1)

4i= 2−δi+4−σi+5 + 1

t(t+ 1)

2= 2−δi+4−σi+5

2−δi+4 + 1

2= 2−σi+5

Continuing the calculations, we obtain

σi+4 ≥1−2−δi+4−1/ln 2

from Theorem 1 and the last estimate implies

δi+4 >2

By considering three units between zeros, we obtain

the following matrix:







2−1 0 0 0 0 0

0 2 −s0 0 0 0

0 0 2 −1 0 0 0

0 0 0 2 −1 0 0

0 0 0 0 2 −1 0

0 0 0 0 0 2 −t

0 0 0 0 0 0 2







The inverse of this matrix is given by:

We can also observe that the number of zeros is greater than

the number of ones, which implies the statement of the theorem.

Theorem 3. Let

an=

i=0

γi2i, n > 1000, γi∈ {0,1},

then

∃j∗<10,and a4n−j∗< an.

Proof. Introduce operators defined as follows:

P f =f

2, T f = 3f+ 1, Zf = 3f,

Ti∈ {P, T }, Ri∈ {Z, P }.

Consider all possible Collatz sequence behaviors

that can be written as follows:

an+n=T1T2. . . Tnan,

Indeed, according to the Collatz rule, the operator

Pis applied if the least significant bit in the binary

representation is zero, and after division, this zero dis-

appears. Conversely, the operator Tis applied when

the least significant bit is one. The action of operator

Tincludes multiplication by two, followed by addi-

tion. This multiplication increases the number of ze-

ros by one due to the bits shifting to the left. During

addition, the number of zeros can only increase.

We explore this through three scenarios:

• In the first case, where zeros are interspersed with

ones, addition results in a series of ones replacing

the interspersed zeros and ones. In the next step,

all but one will turn into zeros.

• In the second case, where zeros and ones occur in

blocks of more than one element, the shift again

adds one more zero. Upon adding to the shifted

number, pairs of ones transform into pairs of ze-

ros, ensuring the number of zeros does not de-

crease.

• In the third case, mixed states are possible, which

also increase the number of zeros after a step.

Using these considerations, we proceed to construct

estimates. We aim to calculate an estimate for every

2n-th member of the Collatz sequence based on the

number of operators P,T,Zapplied during nsteps.

an+n=TnTn−1. . . T1an,

Let anhave mones in its binary representation, then

count the number of Zoperator applications by the

following formula:

m=X

Ri=Z,

i≤n

PROOF

DOI: 10.37394/232020.2024.4.7

Durmagambetov A.A, Durmagambetova A.A

E-ISSN: 2732-9941

Volume 4, 2024

and the number of Poperator applications by the fol-

lowing formula:

Ri=P,

i≤n

1 = m+n−m=n.

Since each Zapplication is followed by a Popera-

tor, and the number of Poperator applications corre-

sponds to the number of zeros in an, which is n−m.

According to the Collatz rules, after nsteps we have:

an+n=3m

2nan+TnTn−1. . . T11 = 3m

2nan+Bn,

Bn≤2−n+m

j=1

2jan<

2−n+m·3m/2m·an≤2−2n+1 ·3m·an.(16)

According to the last formula, we see that the

growth of each sequence member depends on the

number of ones in its binary representation. Next, we

show that a large number of ones on the 2n-th step

leads to an increase in the number of zeros on the 3n-

th step for the binary representation, according to the

previous theorems, which implies a decrease in sub-

sequent sequence members:

a2n= 3man·2−n+Bn= 3m+ 3m(an−2n) + Bn,

Repeating the reasoning of Theorem 2, consider

the equation

2x=a2n= 3man·2−n+Bn=

3m+ 3m(an−2n)·2−n+Bn,(17)

xln 2 = mln(3)+ln 1+(an−2n)·2−n+Bn·3−m,

From the last equation, to apply the results of theorem

2, we need σ1>1

2ln 2. To satisfy the last inequality,

consider mj=m−j, θ = (an−2n)·2−n,

{x}=min

j<10

textbfig{(m−j)ln(3)

ln(2) +

ln(1 + θ)

ln 2+Fj1

2nln 2o,(18)

Consider p= (m−j)ln 3

ln 2= (2k+

l)1.5849625007 . . . , ϵ = 1.5849625007 . . . −1.5,

we get

p= (2k+l)(1.5 + ϵ+ln(1 + θ)

ln 2) =

3k+ (2k+l)·ϵ+ln(1 + θ)

ln 2,(19)

m∗number of non-zero γi,

According to theorem 2 we get

m∗≤n/2 + (n−j∗)·ln 3/ ln 2/2,

According to our application of the Collatz rules, we

have an element a4n−j∗, and the order of its binary

representation is

n2=n+ (n−j∗)·ln 3/ ln 2/2,

After 3n−j∗steps of applying the Collatz rules we

have

a4n−j∗=3m∗

22n−j∗a2n+T3n−j∗T3n−1−j∗. . . T11 =

3m∗

22na2n+B3n,(20)

a4n−j∗=3m∗

22na2n+T3n−j∗T3n−j∗−1. . . T11 =

3m∗

22n3m

2n−j∗an+Bn+B3n−j∗,(21)

a4n−j∗= 3m∗+m·2−3n−j∗an+3m∗·2−2n−j∗Bn+B3n−j∗,

a4n−j∗≤q1·an,

By the definition of m∗, l∗, Bnwe obtain

q1<1,

Using n > 1000, it follows that q1<1⇒a4n−j∗<

an.

Theorem 4. Let

an=

i=0

γi2i, n > 1000, γi∈ {0,1},

then for anthe Collatz conjecture holds.

Proof. The proof follows from Theorems 1-3.

Conclusion

Our assertion proves that after 3n−j∗steps, the se-

quence with an initial binary length of narrives at a

number strictly less than the initial one, thus resolving

the Collatz conjecture. Since applying this process n

times will inevitably lead us to 1.

PROOF

DOI: 10.37394/232020.2024.4.7

Durmagambetov A.A, Durmagambetova A.A

E-ISSN: 2732-9941

Volume 4, 2024

References

[1]. O’Connor, J.J.; Robertson, E.F. (2006). ”Lothar

Collatz”. St Andrews University School of

Mathematics and Statistics, Scotland.

[2]. Tao, Terence (2022). ”Almost all orbits of

the Collatz map attain almost bounded val-

ues”. Forum of Mathematics, Pi. 10: e12.

arXiv:1909.03562. doi:10.1017/fmp.2022.8.

ISSN 2050-5086.

This research has been/was/is funded by the Science

Committee of the Ministry of Science and Higher Ed-

ucation of the Republic of Kazakhstan (Grant No.

AP19677733)»

Contribution of Individual Authors to the

Creation of a Scientific Article (Ghostwriting

Policy)

The authors equally contributed in the present

research, at all stages from the formulation of the

problem to the final findings and solution.

Sources of Funding for Research Presented in a

Scientific Article or Scientific Article Itself

Conflict of Interest

The authors have no conflicts of interest to declare

that are relevant to the content of this article.

Creative Commons Attribution License 4.0

(Attribution 4.0 International, CC BY 4.0)

This article is published under the terms of the

Creative Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en

_US

PROOF

DOI: 10.37394/232020.2024.4.7

Durmagambetov A.A, Durmagambetova A.A

E-ISSN: 2732-9941

Volume 4, 2024