The Collatz Conjecture as a Fractal
The Collatz conjecture (or hailstone problem or 3n+1 problem) is a problem that is so simple to state that grade-schoolers can understand it, yet has been approached from an innumerable variety of angles and has resisted mathematicians for decades now. The problem is as follows:
Pick a positive integer. If it’s even then divide it by 2. If it’s odd, multiply it by 3 and add 1. Now apply this procedure to the result. Repeat. Will you always eventually hit 1 if you continue in this way?
For example, if you start with 11 then you multiply by 3 and add 1 to get 34, divide by 2 to get 17, and continuing similarly gets you the rest of the sequence: 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Before you go trying to find a counterexample to the conjecture, know that it has been verified by computer search for all starting numbers up to 20 × 258 ≈ 5.764 × 1018. The way that we are going to look at this problem today is the “pretty” approach; we’re going to extend the Collatz conjecture over the complex plane and look at the fractal defined by its iteration.
Define the Collatz function f(x) as follows:
Take a moment or two to convinve yourself that if x is a positive integer, then f(x) is the next number after x in its Collatz sequence (e.g., f(11) = 34, f(34) = 17, and so on). To extend this function to the real numbers, simply recall that (-1)x = cos(πx). In fact, this gets us an extension to the complex numbers at the same time, and after some simplification we arrive at:
Well hey, that’s a holomorphic function so it has a notion of a Julia set and we can study the fractal that its iterates induce. Indeed, we can obtain the following image pretty easily with standard fractal-generation software:
The Collatz f(z) fractal
The fractal is located on the complex plane, and the horizontal line through the middle of the image is the real line. Black regions are regions in which the orbit of that number is bounded, while other colours indicate that the orbit of that number is unbounded (notice the large region of bounded numbers around z = 0). The big “spikes” that occur along the real line are, as we would expect, located at the integers (the image above is wide enough that you can see the spikes at z = -2, -1, 1, and 2). Instead of proceeding with the Collatz function as I have defined it, I’m going to introduce a modified Collatz function g(z) as follows:
Observe that this function, like f(z), always maps natural numbers to terms that appear later in their Collatz sequence (e.g., g(11) = 17, g(17) = 13). The benefit of this function is that it has the additional property that g(1) = 1. That is, 1 is a fixed point of g(z), whereas it is part of a period-3 cycle of f(z). The fractal induced by g(z) is:
The Collatz g(z) fractal
Close-up of the g(z) fractal at z = 1
I originally moved to using g(z) instead of f(z) because the plot of the f(z) fractal from earlier indicated to me that there may be a ball of black (i.e., boundedness) of non-zero radius around each of the integers, but proving this for f(z) seemed to be quite difficult (as we would expect, since it would basically imply half of the Collatz conjecture). Somewhat strangely, even though there appear to be balls around the integers in the fractal induced by f(z), these balls vanish in the fractal induced by g(z). The image to the right is a close-up of the above fractal (the point of convergence is z = 1).
Nonetheless, the real line still seems to behave reasonably nicely under the action of g(z); it’s not difficult to prove that the fractal contains the real line segment [0,N] for some large number N that is similar in magnitude to the least M such that the conjecture is true for all n ≤ M (known to be at least 5×1018 or so, as mentioned earlier). However, many (non-natural number) points in that interval do not converge to 1.
So what now? If the Collatz conjecture is true, then z = 1 is the unique natural number fixed point of g(z), yet there seem to be points arbitrarily close to z = 1 that don’t even converge under iteration of g(z). Why are there smaller spikes between the integers in both of these fractals, and where are the spikes centered? Does the restriction of the Collatz function to the numbers at the center of those spikes have any simple interpretation? Who knows, I’ll explore some more in the future. Until then, enjoy some pretty pictures.
g(z) fractal at z = 4
g(z) fractal at z = 8
g(z) fractal at z = 16
g(z) fractal at z = -8
Wiki actually mentions this approach – http://en.wikipedia.org/wiki/Collatz_conjecture#Iterating_on_real_or_complex_numbers – one would assume that there’s some actual research into it already? Or at least some speculation. Although I *still* don’t know complex analysis, but your rephrasing to g(z) seems interesting.
Ha, go figure I make a post about something that’s described a fair amount in a wiki page that I even linked to. Unfortunately it doesn’t seem to have a reference to anything like this so I’m not sure what exactly is known. Oh well, at least it gave me an excuse to make some pretty pictures.
PS. How do you not know any complex analysis yet — aren’t you at McGill (ie. the school the scares the bejesus out of me because they introduce you to abstract algebra in first year)? What year are you in now by the way (I should really know this, I apologize)?
Nah, it’s okay, no one really knows what year I’m in! Let’s say I’m about 18 credits off from graduation, and I have been in university for 2 full years. I’ll probably go over the minimum credit requirement and finish in the spring anyway (I’m told it’s okay because I have no electives >.>) And, well, I don’t know complex analysis because I have a somewhat reduced math requirement because of my econ major (double-majoring, if you recall). It’s not technically mandatory, although I might take it this fall or winter anyway. Also, I’ve focused more on the umm… applied, I suppose, aspects of math (since I’m sort of thinking of going into finance, perhaps). So, I’ve taken courses in stochastic processes, non-linear dynamics, and graph theory, but still no complex analysis.
Also, while wiki doesn’t cite sources, Google scholar provides a few results, although I haven’t exactly read through them. Very little is new under the sun, I suppose (especially in well-researched areas ;)). http://scholar.google.ca/scholar?&q=Collatz+fractal
Your pretty pictures have all but disappeared. 🙁
@Michael Blackburn – Thanks for letting me know. I moved my site to a new server yesterday and some random things like that got lost in the switch. Fixed now 🙂
Did you notice that in your z=4 pic there are 8 “spikes. And in the z=8 pic there are exactly 16 spikes. And in the Z=16 pic there are exactly 32 spikes. ??? makes me wonder if every z=2^n pic will have exactly 2^(n+1) spikes. Neat project!
I like to know what software you had used to generate fractal surface of f(z) and g(z )at z= one integer value. Moreover is it possible to get fractal image of 3x + 1 or 3z+1 mapping at discrete values.
@Rammohan.R – It was a while ago now, but I believe I used Ultra Fractal.
Sending e-mail address where related article published
http://hosting.udlap.mx/profesores/miguela.mendez/alephzero/archivo/historico/az60/granizo60.html
Great article! This morning I was thinking about whether anyone had thought about examining the Collatz conjecture with fractals and I found your blog. Keep up the good work 🙂
Heh. I’ve just started writing my new blog about collatz problem and I came on this site by case. And I’ve just seen that your blog looks almost the same like mine and whats more you have writing about quite the same topics like me. Interesting correlation…
Very neat article. I wasn’t expecting the google query “collatz conjecture extended to reals” to be so fruitful.
Do you know (or intuit) whether or not the convergent set is fully connected? It *looks* like there are islands in the images for z=4, z=8, and z=16, but is it possible that their unconnected appearance is a rendering artefact?
Nice! I watched Veritasium’s YouTube video about Collatz conjecture and immediately Googled for its fractal emanation, and found your article. Thank you for doing this all those years ago!
The Collatz functions show up only as “Collatz function”, “Complex Collatz function”, and “Modified Collatz function”. Could this be changed to show the actual functions? Thanks. I would really like to understand your article better.
@John, the link to the image file containing the function definition is broken. (It seems to be using an old host name.) Here’s the correct link:
http://njohnston.ca/wp-content/uploads/2009/06/img2.gif
It would be great if these image links could be fixed.
Glad I stumbled upon this. I’ve been staring at the numbers using basic math over the last few months and came to the conclusion that the 3n+1 conjecture is a fractal. I have in mind the overall shape that unfolds as the numbers increase. Created shortcuts to get from higher numbers to one and found patterns which prompted me to find the overall pattern.
Looks like a fractal!
@Neil Mayhew – Thanks, fixed now.
There’s a mistake in your definition of the Collatz function, it should be
(1 + (-1)^x) * x / 4 + (1 + (-1)^(x + 1)) * (3 * x + 1) / 2
(i.e. the second exponent should be x+1 rather than x).