0

Is there some sort of algorithmic process or equation to determine the number of steps required for any given integer n to reach 1 in the Collatz Conjecture without having to actually perform a massive amount of number crunching?

I'm talking about when you have to evaluate large numbers like $\\ 2.64 * 10^{3456}$

Greg
  • 561
  • 7
    No one on this planet even knows if the number of steps is finite. – Christopher Carl Heckman Apr 25 '16 at 00:54
  • I'm not sure what you mean in the second sentence, since the Collatz conjecture only deals with integers. Still, there's very little known about the conjecture; we can't even prove that each integer takes a finite number of steps, let alone compute an effective bound. Nor are there any techniques available for dealing with problems like this. The closest approach might be the work in ergodic theory used to prove that certain subsets of $\mathbb{N}$ contain arbitrarily long arithmetic sequences, but I haven't seen anything results in that direction. – anomaly Apr 25 '16 at 01:55
  • For numbers of certain structures the number of iterations can be directly determined, so for numbers of the form $n=2^m$. For numbers of the form $ n= a \cdot 2^m$ one can at least find the number of iterations down to $n' = a$ similarly. Btw., your number needs 59516 iterations to reach n'=1 ... – Gottfried Helms Apr 25 '16 at 12:07
  • Using Pari/GP the following results occur in less than a second: . . . . . . . . . . . . . . $\small {m=3456;w=10^{m-2};\ n1=260 w; [n,it] = [1, 58968]\ n1=261 w; [n,it] = [1, 62437]\ n1=262 w; [n,it] = [1, 61739]\ n1=263 w; [n,it] = [1, 61907]\ n1=264 w; [n,it] = [1, 59516]\ n1=265 w; [n,it] = [1, 61266]\ n1=266 w; [n,it] = [1, 60325]\ n1=267 w; [n,it] = [1, 60837]\ n1=268 w; [n,it] = [1, 61310]\ n1=269 w; [n,it] = [1, 61491]\ } $ . . . . . . . . – Gottfried Helms Apr 26 '16 at 05:08
  • This is one of the late Paul Erdos' $500 problems: he famously remarked that "mathematics is not yet ready for such problems" – colormegone May 04 '16 at 23:07
  • If you edit your question to change the word determine to estimate then I think reopening this question is justified because then it is crystal clear then what you're asking. I suspect this is what you probably meant and doing so will satisfy the pedants who closed it because they didn't understand, and probably didn't make the effort to try to do so. – it's a hire car baby Jul 28 '17 at 15:16

1 Answers1

2

I'm sure it's not the answer you're looking for, but the only algorithmic process known to work for all tested inputs is to repeatedly apply the Collatz function and count the number of applications required to reach 1. Even that is not proven for very large, untested numbers. That's what it means, that the conjecture is unsolved. If there were an equation for the number of steps then the conjecture might be solved by determining for which inputs the output is infinite.

If you look at Terrence Tao's blog I think he describes the rate at which inputs tend to converge on 1 among other things, but this is not proven for all inputs.

it's a hire car baby
  • 9,243
  • P.S. In Terrence Tao's blog he talks about probability of any given step going up or down. An average rate of convergence on 1 can be calculated from that and therefore you can calculate an average number of steps required for any given input. – it's a hire car baby Apr 29 '16 at 13:15