chat highlight update and collatz quickie

hi all, a few words on recent engagements & some new code.

met & had some long, interesting dialogs/discussions with “RS” on the cs.se chat line. he’s worked with woeginger page algorithms, in particular disproving P=NP claims. he’s built various reductions and has also worked on the factoring→SAT conversion. impressive! (these chat lines are usually pretty quiet and now feel lucky to have struck up a few conversations over the last 1½ yr.) he’s interested in increasing cs.se participation and has already done some work to publicize it on irc chat lines. very community oriented. cool! we also got to chatting about stdized testing in eg public schools. a contentious/controversial topic. he cites interesting papers including this very intriguing one on fast constant multiplication by Dimitrov, Imbert, Zakaluzny.

also a new enthusiastic student “B” showed up to cs.se to promote his new ideas on TSP. alas his questions got some low votes but some of the replies on one were high voted incl a response by CS celebrity PS. and also “phil” from tcs.se, with a few highrated tcs.se questions (quite a feat!), was asking about his P≠NP proof by relativization. it was quite a lively scene/near melee at one pt!

also, just quickly finished Fortnow’s “Golden Ticket” book. its really neat to see this mass market popular science book be released after more than 2decades of personally banging on the problem. a real milestone. he didnt go into excruciating detail but thats part of its appeal. a nice glimpse of it all from an “insider perspective”. he did mention the Razborov monotone lower bounds proof. oh, and I noticed that moshe vardi was credited in the back. wow! knew that name looked familiar! he’s active on the TCS google+ group and even reshared one of my recent links to the group [surely gotta put that on my resume, wink!]. small world! was surfing vardi’s google feed. quite prolific and diverse! one of those rare, busy academics very active in cyberspace!

elsewhere heres a collatz quickie, somewhat a riff on the last idea. imagine bins that start out at “0” and the following simple algorithm. choose the smallest bin and the next integer to resolve, and add that integer’s stopping distance (or distance to a lower value) to that bin. continue. graph the bin #s visited. what would you expect?

one of the most difficult aspects of looking for an inductive pattern in collatz data is that there seem to be no “natural boundaries” between regions. could this be a clear indication of some natural, recurring boundaries?

and oh yeah, this is the 1yr anniversary post of this blog! happy btd! the blog has been a fun project/outlet and is getting significant traffic incl from some other elite blogs out there. cant really ask for much more than that! have some big posts/topics in the queue planned, stay tuned.

def f(n)

	c = 0
	n2 = n
	while (n2 >= n)
		n2 = n2 * 3 + 1
		n2 >>= 1 while (n2.even?) 
		c += 1
	end
	return c
end		
		
a = [0] * 100

n = 3
c = 0
i2 = 0
a2 = 0
10000.times \
{
	z = f(n)
	
	a.min_by
	
	
	i = (0...a.size).min_by { |x| a[x] }
	puts([i, a[i], i - i2, c].join("\t"))
	
	c += 1
	c = 0 if (a[i] != a2)
	i2 = i
	a2 = a[i]
	a[i] += z
	
	n += 2
}