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.

reverse


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.

reverse2

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…

Advertisements

3 thoughts on “collatz reverse tree visualization

  1. Pingback: collatz gamechanger, FINALLY? | Turing Machine

  2. Pingback: a new pair of collatz ideas & striking/promising new visualizations | Turing Machine

  3. Pingback: collatz reverse tree traversal/ visualization revisited | Turing Machine

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