Fork me on GitHub
Math for the people, by the people.

User login

Collatz problem

Collatz, Ulam
Ulam's Problem, 1-4-2 Problem, Syracuse problem,Thwaites conjecture, Kakutani's problem, 3n+1 problem
Type of Math Object: 
Major Section: 

Mathematics Subject Classification

11B37 no label found


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...

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

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

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:

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?

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

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


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.


Let $ K$ be a positive number.
Then there exist odd integer $ n$ such that $ M(n)/n > K$ .

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.

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.

Subscribe to Comments for "Collatz problem"