Questions tagged [collatz-conjecture]
The Collatz Conjecture, also known as the 3n+1 conjecture, is a famous open problem named after Lothar Collatz.
76 questions
63
votes
3
answers
5k
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 $...
- 34.3k
47
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 ...
- 19.6k
36
votes
1
answer
3k
views
Collatz conjecture for numbers of th form $2^n +1$
Everybody has heard of the Collatz conjecture and it is a nice programming exercise to write a function, that calculates for a given number $n$ the number of iterations it takes until one reaches $1$. ...
- 11.1k
35
votes
2
answers
7k
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,173
32
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,...
31
votes
4
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 ...
- 151k
26
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 & \...
23
votes
2
answers
880
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,...
- 9,823
19
votes
3
answers
1k
views
A curious sequence of rationals: finite or infinite?
Consider the following function repeatedly applied to a rational
$r = a/b$ in lowest terms:
$f(a/b) = (a b) / (a + b - 1)$.
So, $f(2/3) = 6/4 = 3/2$. $f(3/2) = 6/4 = 3/2$.
I am wondering if it is ...
- 151k
18
votes
1
answer
3k
views
Assuming the Collatz conjecture is false, what is known about the size of the false set?
If the Collatz conjecture is strongly false, in the sense that there is an infinite orbit, let $S_n$ be the set of natural numbers $\le n$ whose orbit goes to infinity.
If $c=\liminf _{n\rightarrow\...
- 5,103
17
votes
2
answers
1k
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}
\...
- 151k
16
votes
3
answers
4k
views
Is it known that the Collatz-like sequence with 7n+1 diverges to infinity starting with 7?
In this question I was wondering if the $3$ in the Collatz conjecture is arbitrary, and when I wrote that question I tried to change to $7n+1$ starting with the seed number $7$, the sequence appears ...
- 541
15
votes
1
answer
1k
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 ...
- 259
14
votes
3
answers
2k
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 ...
- 261
14
votes
1
answer
426
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 ...
- 37.7k
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 ...
- 1,613
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}$...
- 127
11
votes
1
answer
1k
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 ...
- 3,032
11
votes
1
answer
2k
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 ...
- 28.2k
11
votes
0
answers
809
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)$ ...
10
votes
2
answers
4k
views
Larger cycle than 4, 2, 1 in Collatz iteration?
(Here I discuss the Collatz problem only for positive integers.)
It is possible, by computation, to find all cycles in the Collatz iteration of a fixed length.
It is clear that an increase must be ...
- 3,645
9
votes
1
answer
2k
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 ...
9
votes
1
answer
942
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 ...
- 2,275
9
votes
0
answers
416
views
Reframing Collatz Conjecture as a property of meromorphic functions
I was wondering if it is known that the 3n+1 Collatz conjecture could be reframed as a statement about the set of solutions to a particular equation formulated as the sum of residues. This is ...
- 107
8
votes
1
answer
2k
views
Collatz stopping-time and Poisson distribution, and connection to other problems?
I read many threads about Collatz here - so don't worry, this is no attempt to any proof, just asking about a curious fact:
This graph gives the stopping-time of Collatz sequences up to $n=10^8$
(...
- 91
8
votes
1
answer
259
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 ...
- 1,871
8
votes
3
answers
459
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,...
- 17k
8
votes
0
answers
1k
views
Is the Collatz conjecture known to be true for interesting unbounded classes of 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$...
- 13.9k
7
votes
1
answer
4k
views
Beyond Collatz: A $5n+1$ conjecture? [closed]
Let
$$x_{n+1} = \begin{cases} x_n/2 &;\text{if } x_n \equiv 0 \pmod{2}\\ k\,x_n+1 &; \text{if } x_n\equiv 1 \pmod{2} \end{cases}$$
and $k=3$ and $x_n\in\Bbb N$. Collatz conjectured for this ...
- 254
6
votes
4
answers
487
views
When is $\{b^2 - \{b-1\}_2\}_2=1$ with odd $b$? (The bracket-notation explained below)
For the complete extraction of the factor $p$ and its powers from a natural number $n$
let's define the notation $$ \{n\}_p := { n \over p^{\nu_p(n)}} \tag 1$$
$ \qquad \qquad $ Here $\nu_p(n)$ means ...
- 5,342
6
votes
1
answer
1k
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 ...
- 48.8k
6
votes
1
answer
561
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 ...
- 2,302
6
votes
0
answers
448
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{...
- 1,375
5
votes
2
answers
2k
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). ...
- 2,275
5
votes
1
answer
992
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 ...
- 13.9k
5
votes
2
answers
1k
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,
$...
5
votes
0
answers
363
views
A Collatz-like map?
Consider the map $\psi$ acting on triples $(a\leq b\leq c)$ of three positive natural integers with $\mathrm{gcd}(a,b,c)=1$ as follows:
Set $$(a',b',c')=\left(\frac{a}{\mathrm{gcd}(a,bc)},\frac{b}{\...
- 17.9k
5
votes
0
answers
172
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 ...
- 17.9k
5
votes
0
answers
342
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.
$$
...
- 1,645
4
votes
1
answer
2k
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 ...
- 188
4
votes
1
answer
370
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 ...
- 1,087
4
votes
0
answers
504
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 ...
- 3,032
4
votes
0
answers
447
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$ ...
4
votes
0
answers
382
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)$, ...
3
votes
1
answer
2k
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 ...
- 48.8k
3
votes
2
answers
436
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 ...
- 263
3
votes
0
answers
174
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 ...
- 19.6k
2
votes
1
answer
1k
views
Reference on the Collatz conjecture [closed]
I'm just looking for references in the literature for some observations I made for fun about the Collatz conjecture.
The Collatz conjecture states that any positive integer $n$ can eventually be ...
- 179
2
votes
1
answer
266
views
A problem similar to the $3x+1$-problem [closed]
Let $n$ be a fixed positive integer. Define the function $f_n(x)$ as follows:
$$f_n(x)=\left\{\begin{aligned}&2x-1,\quad x\leq n;\\&2(x-n),\quad x> n.\end{aligned}\right.$$
and for $l\in\...
- 111
2
votes
2
answers
620
views
A mutation of the Collatz disease
Given $k \in \mathbb N$, we define $f_k: \mathbb N \longrightarrow \mathbb N$ by
$$ f_k(x) = \begin{cases} \,\quad\dfrac{x}2 &\text{ if } x \text{ is even} \\\\ \dfrac{3x+3^k}{2} & \text{ if } ...
- 17.9k