# collatz reverse tree visualization

hi all. there are many ways to visualize the collatz problem. not sure when stumbled across a particular very nice visualization [possibly as one of the top results in a google search!]. was thinking about different directions & reminded of it this week and then found it again via google.

its by jason davies, and shows a remarkable symmetry, via a spherical attractive/repulsive force plotting of the reverse-order tree. the tree is built in reverse order of trajectories, starting from 1.[1] alas, presumably not symmetric enough to turn into a proof. but it does show the basic idea of using visualization and datamining to find exploitable patterns/structure. featured on oreilly “visualization of the week” oct7 2011.

this gave me the idea for this new very simple program. its similar to the davies visualization. it starts at 1 and goes in reverse for the smallest value in the current list. it outputs new “resolved” integers as they are found. there is a strong connection to the davies graph and quite a bit of structure.

```
l = [1]
seen = {}
c = 0

loop \
{
l.sort!

#	p(l)
x = l.shift
l2 = [x * 2]
l2 << (x - 1) / 3 if (x != 1 && x != 4 && (x - 1) % 3 == 0)
l2.each \
{
|y|
next if (seen.member?(y))
p(y)
l << y
seen[y] = nil
c += 1
exit if (c == 5000)
}
}

```

know how clouds look like shapes when you’re a kid? or rorschach tests? hmmm, it looks kinda like a fence with semiregular bumpy/wobbly fenceposts going off to infinity. another slight variation, advancing the $x$ coordinate only when a new $y$ coordinate maximum is found, “straightens out the fenceposts” and leads to this graph.

```l = [1]
seen = {}
c = 0
mx = 0
z = 0

loop \
{
l.sort!

#	p(l)
x = l.shift
l2 = [x * 2]
l2 << (x - 1) / 3 if (x != 1 && x != 4 && (x - 1) % 3 == 0)
l2.each \
{
|y|
next if (seen.member?(y))
puts([z, y].join("\t"))
l << y
seen[y] = nil
if (y > mx) then
mx = y
z += 1
end
c += 1
exit if (c == 5000)
}
}
```

* * *

there are so many ways to visualize the collatz conjecture, it would be very interesting to create a directory of different visualizations. actually, riffing off that a little, a glossy/colorful coffee table book on “number theoretic fractals” would really be way cool eh?

another neat recent development/highlight, the TCS question by reyzin, “a simple problem whose decidability is not known”[4] with a remarkable/striking 37 votes as of writing & some contributions by yours truly [more great blog fodder, maybe more on that some other time]. new TCS.se questions with high votes are really rare these days, it seems one gets over 10-20 only rarely, like once a month at best. discovering a new question with high votes seems like a real event. also, Turkistany cited the collatz problem in a comment that got 19 upvotes. but then he wrote it up as an answer, and it currently has one vote by (dramatically pulling down the mask) yours truly!

stackexchange voting can be really crazily capricious sometimes…. with most questions in the sub-5 vote range, it does tend to show theres a significant mostly dormant audience there that is “mostly bored” with the questions asked. also, there appears to be a “winner takes all” power-law like distribution of votes. it would be very fun to do datamining on that data. [which reminds me, stackexchange did announce a cool new dataminer position/competition, intend to write about that some time.]

as I mentioned recently the collatz problem seems to naturally relate to fractals, although am not really aware of papers on the subject linking the two, but havent searched too much [so far].

elsewhere, via the TCS aggregator ran across the neat new paper finding and analyzing fractal properties in TM computational tableaus[2], something [an idea/concept/angle] that seems to have been pioneered by Wolfram but would be hard pressed to cite a paper of his. [3] is a brief recorded musing on the subject/connection that was not well-received at the time. as is sometimes said the pioneers are the ones with the arrows in their backs…