## You are here

HomeCollatz problem

## Primary tabs

# Collatz problem

We define the function $f:\mathbb{N}\longrightarrow\mathbb{N}$ (where $\mathbb{N}$ excludes zero) such that

$f(a)=\left\{\begin{array}[]{rl}3a+1&\text{ if }a\text{ is odd }\\ a/2&\text{ if }a\text{ is even.}\end{array}\right.$ |

Then let the sequence $c_{n}$ be defined as $c_{i}=f(c_{{i-1}})$, with $c_{0}$ an arbitrary natural seed value.

It is conjectured that the sequence $c_{0},c_{1},c_{2},\ldots$ will always end in $1,4,2$, repeating infinitely. This has been verified by computer up to very large values of $c_{0}$, but is unproven in general. It is also not known whether this problem is decideable. This is generally called the *Collatz problem*.

The sequence $c_{n}$ is sometimes called the “hailstone sequence”. This is because it behaves analogously to a hailstone in a cloud which falls by gravity and is tossed up again repeatedly. The sequence similarly ends in an eternal oscillation.

## Mathematics Subject Classification

11B37*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier

## Comments

## Collatz Problem

This has been a conjecture that has stuck in the back of my mind for a very long time. Was reading some literature on it the other day, and it seems that someone has come up with a topological characterization. Basically, all the orbits of the Collatz function form a basis for a topology on the positive integers induced by this function. A corollary to a theorem states that the Collatz Conjecture is true if and only if the topology induced by the Collatz Function on the positive integers is connected. Another interaction of number theory, topology and dynamical systems...

## Re: Collatz Problem

So is there some chance that this will open the door to proving it? (Or has it been proved undecideable? I forget)

-apk

## Re: Re: Collatz Problem

Oh, it hasn't been proven undecideable (read my own object, duh)

-apk

## Re: Re: Re: Collatz Problem

It seems now that the resolution (in the topological attack) lies in proving that the Collatz Graph of a given function f is weakly connected if and only if the topology induced by f is connected. For an outline of the ideas see:

http://www.math.grin.edu/~chamberl/conference/papers/monks.pdf

## Re: Re: Re: Collatz Problem

My god, I am so lost. Course, thats probably because the highest math that I've been exposed to is Trig. But I'm working on that.

So, if it isn't too much trouble, could someone give me some background information on what the paper means, in laymans English? Or at least some pointers to other papers which could help me in trying to understand this problem?

## Re: Re: Re: Collatz Problem

http://planetmath.org/encyclopedia/CollatzProblem.html

http://en.wikipedia.org/wiki/Collatz_conjecture

## Re: Collatz Problem

You will find that Kenneth Conrow has posted a proof and accompanying documentation of the binary tree structure and the State Transitions of same at

http://www-personal.ksu.edu/~kconrow/index.html

It is a tree structure that is better than weakly-connected, and more than is required to establish the proof.

Joe

## Is following theorem known?

Let $ S$ be the set of odd positive integers.

We define $R:S \longrightarrow \ S $ such that $R(n) = (3n+1)/2^r$, with $ r$ as large as possible.

Next we define $ M(n)=sup(n,R(n),R(Rn)),...}$ for every odd positive integer.

Then

THEOREM

Let $ K$ be a positive number.

Then there exist odd integer $ n$ such that $ M(n)/n > K$ .

## Re: Is following theorem known?

I think you can prove it by making the following handwaving argument work: let n = 2^s -1, for some positive integer s

Then 3n + 1 = 3.2^s - 2, which is divisible by 2 exactly once. So R(n) = 3.2^{s-1} -1

Similarly R^2(n) = 3^2. 2^{s-2} -1....and so on

the point being that the value of R(n) is increasing by a factor of about 3/2 each time. So R^k (n) /n is about (3/2)^k, so long as k < s

If you make s big enough, you can therefore make R^k (n ) /n as big as you like.

## Re: Is following theorem known?

Thank you for your replying.

I proved the theorem at thinking of n = k.2^(s+1) + (2^s-1) as you wrote.

Then I found R(n) > (3/2).n and R(n)=(3k+1).2^s + (2^(s-1)-1) , so the theorem follows.

Thank you.