## Collatz related question [closed]

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

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

## 1 Answer

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?

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9227714538574219, "perplexity_flag": "middle"}