# Questions tagged [collatz-conjecture]

The Collatz Conjecture, also known as the 3n+1 conjecture, is a famous open problem named after Lothar Collatz.

58
questions

3
votes

0
answers

51
views

### The two Collatz-maps associated to characters modulo 8

Given a Dirichlet character $\chi$ modulo $8$ we consider the map $\mu(x)=x/2$ if $x$ is even and $\mu(x)=(3x+\chi(x))/2$ otherwise.
(The corresponding map for $\chi$ the trivial Dirichlet character ...

1
vote

0
answers

127
views

### Has the Collatz been investigated as a recursive function?

Does anyone ever write the Collatz conjecture as a single algebraic, recursive sequence? For example, a crude version might be:
$$
g(n+1)=\delta _{1,g(n)}+(1-\delta _{1,g(n)})*\left(\left(\frac{cos(\...

0
votes

1
answer

313
views

### Can anyone recommend a reference where the collatz conjecture is viewed as a combinatorics problem?

It occurs to me that the question about whether non-trivial cycles exist for the collatz conjecture can be restated as these two questions (details on how this relates to the collatz conjecture can be ...

0
votes

1
answer

433
views

### Polynomials, $3^x$ and the Collatz conjecture

$\DeclareMathOperator\Orb{Orb}\newcommand\abs[1]{\lvert#1\rvert}$The Collatz or the $3n+1$ conjecture is open.
Are there non-trivial polynomials $f(x)\in\mathbb Z[x]$ and $g(x)\in\mathbb R[x]$ having ...

6
votes

0
answers

646
views

### Is Collatz conjecture known to be true for specific numbers?

The Collatz or the $3n+1$ conjecture is open.
Is there a specific polynomial $f(x)\in\mathbb Z[x]$ whose range is unbounded for which every integer of form $|f(m)|$ at $m\in\mathbb Z$ satisfies $3n+1$...

-1
votes

1
answer

548
views

### Can you explain this weird pattern in Collatz conjecture? [closed]

Extreme disproportion in the dispersion of "Digital Roots" of the highest numbers reach in the Collatz Conjecture.
I calculated the Digital Root remainder mod 9 for the highest numbers ...

4
votes

1
answer

1k
views

### Summary of “Almost All Orbits of the Collatz Map Attain Almost Bounded Values”

Terence Tao's 2019 paper ``Almost all Orbits of the Collatz map attain almost bounded values" is pretty famous. However, it's also long and complicated. I think there are useful techniques to ...

1
vote

0
answers

358
views

### Does this iterating process always returns to 0 for positive $a_0$?

Given $a_0$ be an positive integer, define
$$ a_{n+1} =
\begin{cases}
8a_n, & \text{if $a_n$ is odd} \\
\lfloor a_n/3\rfloor, & \text{if $a_n$ is even}
\end{cases}$$
Now form the sequence $(...

2
votes

0
answers

230
views

### Surreal numbers and the Collatz iteration as a game?

Let us define a game based on the Collatz function $C(n) = n/2$ if $n$ is even, otherwise $=3n+1$.
Each number $n$ represents a game played by left $L$ and right $R$:
$$n = \{L_n | R_n \}$$
The rules ...

10
votes

1
answer

688
views

### Generating functions of Collatz iterates?

Let $C(n) = n/2$ if $n$ is even and $3n+1$ otherwise be the Collatz function.
We look at the generating function $f_n(x) = \sum_{k=0}^\infty C^{(k)}(n)x^k$ of the iterates of the Collatz function.
The ...

4
votes

0
answers

396
views

### Collatz conjecture and a diophantine equation

Let $M \ge 2$. Inspired by the Collatz iteration / algorithm ($M=2$), I tried the following function:
$$C_M(n) = n/M, \text{ if } n \equiv 0 \mod M, \text{ otherwise } (M+1)n+\{(M-n) \mod M \}$$
We ...

6
votes

1
answer

781
views

### Generalized Collatz sequences

Let $\mathbb{N}$ denote the set of positive integers. For $k\in\mathbb{N}$ let $c_k:\mathbb{N}\to\mathbb{N}$ be defined by $x\mapsto x/2$ for $x$ even and $x\mapsto kx+1$ otherwise. The Collatz ...

1
vote

1
answer

340
views

### What is the quotient (pseudo)metric $d_\sim$ and how do I identify the infimum of possible sequences in this instance?

Let $Z$ be the the set of dyadic and ternary rationals in the interval $\left[\frac12,1\right)$ whose 3-adic valuation is either $-1$ or $0$, with the standard absolute value topology inherited from ...

1
vote

0
answers

894
views

### Collatz conjecture in all its variants

There are all kinds of execution variants to the collatz conjecture for when hitting an odd number:
$3n+1$ or $3n+3^a$ or $1.5n + 0.5$ or $1.5n + 1.5$... . The assumption is: proving any of them will ...

5
votes

1
answer

865
views

### Does this prove Collatz is a $\Sigma_1$ problem?

So I got an email from one of my colleagues on the Collatz Conjecture with a link to the article Computer Scientists Attempt to Corner the Collatz Conjecture by Kevin Hartnett in Quanta Magazine.
On ...

5
votes

0
answers

248
views

### Heuristic for a density conjecture related to the Collatz $(3x+1)$-problem

First, some notation. Define $T(n)$ over $n\in \mathbb{N}$ as:
$$
T(n) = \left\{ \begin{array}{}
3n+1, & \text{if $n$ is odd}\ \\
n/2, & \text{if $n$ is even}
\end{array} \right.
$$
...

4
votes

2
answers

312
views

### A possibly easy question about latent geometry in Collatz sequences

I have a question about some (seemingly unimportant) behavior I noticed in Collatz sequences, which I haven't been able to find a general answer to upon rough scan of the literature (please be aware ...

2
votes

0
answers

376
views

### The irrational numbers α such that n odd and m=⌊nα⌋ odd implies ⌊mα⌋ odd

This post is the analogous of that one (about $\sqrt{2}$) but with a much stronger expectation here.
We observed, and then this comment of Lucia proved, that for $\phi$ the golden ratio, if $n$ ...

24
votes

3
answers

2k
views

### Unexpected behavior involving √2 and parity

This post makes a focus on a very specific part of that long post. Consider the following map:
$$f: n \mapsto \left\{
\begin{array}{ll}
\left \lfloor{n/\sqrt{2}} \right \rfloor & \...

9
votes

0
answers

625
views

### Borderline Collatz-like problems

The usual Collatz map is $C:n \mapsto n/2$ if $n$ even, $(3n+1)/2$ if $n$ odd. Let $f^{\circ (r+1)}:=f \circ f^{\circ r}$.
We suspect that for every fixed $n>0$, the sequence $C^{\circ r}(n)$ ...

15
votes

1
answer

981
views

### Arithmetic progressions in stopping time of Collatz sequences

Inspired by the question here, we did a few more simulations of numbers of some specific forms and noticed a pattern.
We consider the original $3n+1$ transform where we divide by $2$ if it's even and ...

5
votes

2
answers

937
views

### Proof that $3^ns + \sum_{k=0}^{n-1} 3^{n-k-1}2^{a_k}=2^m.$

How would I go about proving the following:
For any odd positive integer $s$, there exists a sequence of nonnegative integers $( a_0, a_1, \cdots, a_{n-1})$ and a nonnegative integer $m$ such that,
$...

12
votes

1
answer

1k
views

### Explicit bounds from Tao's result on Collatz conjecture

A new preprint by Terry Tao has recently appeared and has established some interesting results regarding the topic of Collatz conjecture. I will not cite the precise result, but rather an equivalent ...

2
votes

1
answer

377
views

### A complementary of the Collatz $3x+1$ problem

Let $\mathbb{N}_{\text{odd}}$ be the set of odd positive integers. For $x_0 \in \mathbb{N}_{\text{odd}}$
consider the set-valued sequence $\{A_n\}_{n=0}^{\infty}$ defined by the formula
$$
A_0 = \{...

3
votes

1
answer

1k
views

### Two reasons why the Collatz conjecture could fail

Let $\mathbb{N}$ denote the set of positive integers. The Collatz function $f:\mathbb{N}\to\mathbb{N}$ is given by $f(n) = n/2$ for $n$ even and $f(n) = 3n+1$ for $n$ odd. Given $k\in\mathbb{N}$ we ...

8
votes

1
answer

231
views

### For which primes does this iterated function act transitively? (Sort of a finite analogue of Collatz conjecture.)

Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property ...

24
votes

2
answers

4k
views

### Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?

Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.
Goldbach's conjecture asserts that every ...

-1
votes

2
answers

354
views

### Are there integral solutions for $(2a-1)(2^{(b+c)}-3^c )=2^b-1$?

Can anyone prove this assertion? Or at least suggest a method of attack? It has come up in my research.
There do not exist $a,b$ and $c$ such that$$
(2a-1)(2^{(b+c)}-3^c )=2^b-1
$$where $a>0,b&...

8
votes

3
answers

411
views

### Density of the Klarner-Rado Sequence

Consider the Klarner-Rado sequence OEIS A005658 defined by the rule: the sequence starts with 1, and if it contains $n$ it also contains $2n$, $3n+2$ and $6n+3$. According to R. Guy's popular article,...

4
votes

0
answers

246
views

### How can I catalog these generalized Collatz problems?

The Collatz conjecture can be expressed in terms of a ruleset in the language $\{x,+,1,\rightarrow,;\}$:
$x + x + 1 \rightarrow x+x+x+1+1;$
$x + x \rightarrow x;$
Whenever a number matches the LHS ...

4
votes

0
answers

305
views

### Extension of Coburn's theorem on isometry and Toeplitz algebra

$\newcommand{\id}{\mathrm{id}}$Let $H$ be a Hilbert space, and $X \in B(H)$ a proper isometry (i.e. $X^{\star}X = \id$ and $XX^{\star} \neq \id$). Coburn's theorem states that ${\rm C}^{\star}(X)$, ...

7
votes

1
answer

1k
views

### A problem involving the inverse Collatz map

Let $C$ be the Collatz map on the natural numbers, defined by:
$$C(n) :=
\begin{cases}
n/2 & \text{if} \;n \;\text{even} \\
(3n+1)/2 & \text{if} \;n \;\text{odd}
\end{cases}$$
The inverse ...

3
votes

2
answers

355
views

### Identification of Invariant Sets for Discrete Dynamical Systems on the Positive Integers

Let $\phi:\mathbb{N}\times \mathbb{N}^+\rightarrow \mathbb{N}^+$ be a dynamical system on the positive integers. Suppose we refer to the orbit of a periodic point of $\phi$ as an invariant set of the ...

12
votes

3
answers

2k
views

### Undecidable easy arithmetical statement

Is there a basic arithmetic statement which is known to be undecidable ?
By basic arithmetic statement I do mean an easy statement in the spirit of the Collatz conjecture . By the way is there some ...

0
votes

1
answer

289
views

### Are there infinitely many solutions of $2^k=3^z-1$ with $k,z \in \mathbb{N}$? [duplicate]

This question arose as an attempt to answer the following question Relaxed Collatz 3x+1 conjecture. I wanted to show that there is a solution of the equation $2^{k}=3^{z}(2n+1)-1$ for each $n\geq 2$,
...

1
vote

1
answer

455
views

### A Zsigmondy-theorem-analogy in the generalized Collatz-problem $3x+\rho$?

Remark : I've found a rather trivial answer for this question and so very likely the premise of paralleling it with the Zsigmondy-theorem is wrong, so this question might better be retracted. I'll ...

30
votes

2
answers

2k
views

### A Collatz-like problem on prime numbers

Consider the function $f$ on the prime numbers defined by $$ f(p):= \text{ the greatest prime factor of } 2p+1.$$ The iteration of $f$ from any prime $p<10^8$ converges to the cycle $$(3,7,5,11,23,...

22
votes

2
answers

796
views

### Possible behaviors of integer sequences that arise from powering nonnegative integer matrices

Let's call a sequence of nonnegative integers $x_1,x_2,\ldots$ matrix-realizable, if there exists a $k\times k$ nonnegative integer matrix $A$ (for some $k$), as well as nonnegative integer vectors $u,...

12
votes

3
answers

1k
views

### Collatz-like properties of finite fields

I was wondering what an equivalent of the Collatz conjecture might be for finite fields. In a Collatz sequence a number is moved down within a set $\{2^k n : k \in \mathbb{Z}^* \}$ for some odd $n$ or ...

17
votes

2
answers

962
views

### Does 53 diverge to infinity in this Collatz-like sequence?

This function has been explored a bit at MSE (in June 2016):
\begin{eqnarray}
f(n) &=& (n-1)^2 \; \textrm{if} \; (n \bmod 4) = 1\\
f(n) &=& \lfloor n/4 \rfloor \; \textrm{otherwise}
\...

11
votes

1
answer

1k
views

### Some Questions on the Collatz conjecture (reexpressed as "equivalence relation")

The set of all positive whole numbers is denoted by $\mathbb{N}_+$.
Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto
\begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ odd}\end{cases}$...

44
votes

1
answer

3k
views

### Relaxed Collatz 3x+1 conjecture

The Collatz $3x+1$ conjecture claims that any positive integer can eventually be reduced to $1$ by iterative application of the maps $x \mapsto 3x+1$ whenever $x$ is odd and $x \mapsto x/2$ whenever $...

14
votes

1
answer

388
views

### A Collatz-like question about permutations

An answer to this question would provide an explicit counterexample to this question, but otherwise I don't know if it is interesting.
Consider all permutations $\pi$ on the natural numbers such that ...

8
votes

1
answer

803
views

### Residue class sufficiency sets for the Collatz conjecture

I have recently managed to show a sequence of sufficiency sets for the Collatz conjecture whose natural density approaches 0 (the set theoretic limit approaches the set $\{1\}$). It is an extension of ...

44
votes

1
answer

2k
views

### Transitivity on $\mathbb{N}_0$ -- a 42 problem

Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class
transposition $\tau_{r_1(m_1),r_2(m_2)}$ be the ...

6
votes

0
answers

410
views

### Are there always at least *five* divisions?

@JosephO'Rourke asked a question about a Collatz like function related to primes:
$f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is prime} \\
\lfloor n/2 \rfloor & \text{if} \;n \;\text{...

22
votes

3
answers

2k
views

### A Collatz-like function that bifurcates on primes

This is likely piling one mystery on another, but ...
I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows:
$$
f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is ...

-1
votes

1
answer

356
views

### Collatz property implying infinite "fall below" trajectories, is it known?

(this was discovered analyzing Collatz empirically.)
a key aspect of resolving Collatz involves looking at the number of iterations for trajectories to "fall below" the initial value.
consider a ...

5
votes

2
answers

1k
views

### 3n+1 problem and cycles

Just to make sure I am up to date with this problem. I know (or I think I do) that it is not yet proven that there are no non-trivial cycles for the collatz sequence (please correct me if I am wrong). ...

3
votes

0
answers

165
views

### Largest permutation groups without "non-mixing" subgroups

We say that a subgroup of ${\rm Sym}(\mathbb{N})$ has sparse orbit representatives
if it has infinitely many orbits on $\mathbb{N}$, but the set of smallest orbit
representatives has natural density 0 ...