Logarithmic approximations for Collatz

A question from Republic of Math:

 

The fit in this plot looked a bit off to me – it seems like it should be a log, not a square root. (But of course a log is just a zeroth power…) For those who aren’t familiar, the Collatz conjecture is as follows: given an arbitrary positive integer, if it’s even, divide it by 2, and if it’s odd, multiply by 3 and add 1. Repeat. As far as we know, you always end up at 1. For example, say we start with 7; then we get

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

So why should this be true? Consider only the odd numbers in the sequence. In the previous sequence those are

7, 11, 17, 13, 5, 1

where we get each number by taking three times the previous one, plus one, and then dividing by 2 as many times as we can. We can figure that half the time we’ll divide by 2 once, a quarter of the time we’ll divide by 2 twice, and so on; on average we’ll divide by 2 twice. So each number in this sequence should be, on average, about three-quarters of the previous one, and each step in this sequence corresponds to three steps in the previous sequence (one tripling and two halvings). Thus each step on average multiplies by (3/4)^{1/3} and it should take (\log n)/(\log (4/3)^{1/3}) steps to get from n down to 1. Call this C \log n where C = 1/(\log (4/3)^{1/3}) \approx 10.42.

This heuristic argument is in, for example, the review paper of Lagarias; this online HTML version of the same paper gives the additional remark that the stopping time of the sequence is conjectured to be asymptotically normally distributed with mean and variance both on the order of log n. (The constant is different there; that’s because Lagarias goes directly from x to (3x+1)/2 if x is odd.)

Let’s define a function t(n) to be the number of iterations in this process needed to get to 1. For example look at the trajectory for 7 above; it takes 16 iterations to get to 1, so t(7) = 16. Similarly for example t(4) = 2 (the trajectory is 4, 2, 1) and t(6) = 8 (the trajectory is 6, 3, 10, 5, 16, 8, 4, 2, 1). This is the sequence A006577 in the OEIS. Then the original question is about the function m(n) = {1 \over n} (t(1) + t(2) + \cdots + t(n)). But since “most” numbers less than $\latex n$ have their logarithms near $\latex \log n$, that sum can be approximated as just (1/n) (n \times (C \log n)) or $\latex C \log n$.

And indeed a logarithmic model is the better fit (red in the plot below; blue is a power law – in both cases I’ve just fit to the range 100 \le n \le 5000)

running-means-of-collatz-stopping-time

Sadly, we don’t recover that constant 10.42… the red curve is m = -16.87 + 11.07 n and the blue curve is m = 16.31 \times n^{0.185}.  But it’s not like you’d expect asymptotic behavior to kick in by 5000 anyway.

Advertisements

One thought on “Logarithmic approximations for Collatz

  1. Thanks for doing the work. I’d been doing some thinking about the conjecture recently since a friend had a dream-inspired mathematics puzzle that reminded me of it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s