0

Howdy,

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))?

flag
I've voted to close. Your question isn't well formulated. I think you'd be better off asking your question on math.stackexchange.com, but you ought to be a little more careful in its formulation. – Ryan Budney Jun 12 2011 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 2011 at 3:32

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

1 Answer

2

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?

link|flag
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 2011 at 6:18

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