MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


Not sure this will be entirely clear, but when considering the relationship between a start value n in the Collatz algorithm and the length of the sequence generated by n, is there a function f() such that f(n) = y >= length(Collatz(n))?

share|cite|improve this question

closed as not a real question by Ryan Budney, Qiaochu Yuan, Todd Trimble, gowers, Steve Huntsman Jun 12 '11 at 23:35

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I've voted to close. Your question isn't well formulated. I think you'd be better off asking your question on, but you ought to be a little more careful in its formulation. – Ryan Budney Jun 12 '11 at 23:24
This is so close to a good question that I am sorry to see it closed. An answer to the good questionn could be along the lines of "Consider the directed graph which has (n, c(n)) as an edge, where c(n) is either n/2 or 3n+1. The desired length function is the number of edges from n to 4 (or 2 or 1). This is an example of a partial recursive function, for which we do not know if it is total or even (on values where it known to be defined) if it is bounded above by a total recursive function." Perhaps someone will edit it to reopen. Gerhard "Ask Me About System Design" Paseman, 2011.06.12 – Gerhard Paseman Jun 13 '11 at 3:32

The existence of such a function is equivalent to the unproven statement that all n eventually settle into the $4, 2, 1$ cycle. Or do I misunderstand your question?

share|cite|improve this answer
Although I suspect the poster is not asking the following, a nontrivial variant is: Is there an interesting partial recursive function f, an infinite interesting set D of positive integers, and a proof such that for all n in D, the collatz length function c(n) is defined and has a nonnegative value, similarly for f(n), and f(n) > c(n), and the proof demonstrates this? If c(n) is total, then it is recursive, but other than lower bounds, we know nothing of the asymptotic growth rate of c(n). Gerhard "Interesting Will Be Defined Later" Paseman, 2011.06.12 – Gerhard Paseman Jun 13 '11 at 6:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.