another (key?) phase transition in collatz etc

the last post on collatz is getting big and a bit unwieldy. often wish there were better/ more streamlined blog editing capabilities. its a real challenge doing real science using mere blog editors. its not simple figuring out when to do new posts. figure its about time again.

big news, have not mentioned this on the blog yet (other than the sandbox scratchpad version). randomra cited previously as a collatz codegolf fan came up with and posted his own challenge “analyzing collatz like sequences” and it currently has 13v and one submission at 5v. congratulations dude! its a mini research program! ⭐ 😎 😀 ❤

the other significant news is the discovery of (yet another) phase transition, normalizing feature in collatz trajectory binary form max 0-runs, below, building on recent results looking at behavior of max 0-runs (but note those were based on the trajectory parity sequence instead; although they are clearly informally linked). overall its unexpected and striking, much like the early hamming weight/ density results (and surely closely connected, but dont have that all formalized yet). here is a very simple piece of code that analyzes this, and it looks like it could be a very big deal toward a proof to me.

the code just builds random starting seeds using a continuum of randomly selected ‘1’ bits in binary. then it looks at max 0-run length in the prior (red) and subsequent (green) (one “div-2 compressed” evaluation/ iteration). the results are striking. it shows a phase transition. in the left region the new max 0-run length is (apparently/ empircally!) always less than prior, and in the right region it is always more. at the moment this seems another big piece of the puzzle.

again feel a bit embarrassed not to have found this basic property a long time ago. 😳 all the other stuff is cool but have been “getting carried away” with very sophisticated ideas and havent even done statistics 101 analysis/ angles. in defense, 2020 hindsight.


def r(w, c)

	l = [0] * (w - 1)

	l2 = (0...(w - 1)).to_a

	c.times { l[l2.delete_at(rand(l2.size))] = 1 }

	return ('1'+ l.join)

end

def f(x)

	x = x * 3 + 1 if (x.odd?)
	x /= 2 while (x.even?)
	return x.to_s(2)
end

def stat(s)

	j = s.split('1').map { |x| x.length }.max
	return j.nil? ? 0 : j
end

c = 1000

c.times \
{
	|i|
	s = r(c, i)
	s2 = f(s.to_i)
	puts([stat(s), stat(s2)].join("\t"))
}

gap

collatz, brief retrospective/ analysis/ overview/ musings

(4/4) close now to 2 dozen posts over about 2 years (1st post here july 2013, and separate collatz page created april 2013, and actually coming around on ~2 decades of more-or-less personal dabbling on it), over time the collatz category on this blog has swelled beyond initial expectation. here is a brief/ candid summary of the overall “project status”.

  • it is much harder than expected by me. erroneously fantasized that novel/ powerful 21st century type techniques not previously available/ employed might be enough to overpower/ crack it also without arduous/ massive effort. it truly is an Everest-or-Olympic-Mons level challenge. but ofc the math community has long recognized the intense difficulty of this problem. in “big” open math problems its always also an open question of how much extra effort and attention/ collaboration can lead to larger results. are the problems not yielding because key people have not investigated them, or is it the opposite case that very highly qualified/ knowledgeable people have looked into them heavily and failed to get results, possibly not publishing negative results aka failures? the longer one works on them, the more one is inclined to believe the latter.
  • wiles once compared FLT research to bumping around in a dark room; on the other hand Collatz (and other big problems like P vs NP) remind me of the problem of exploring a dark cave of unknown dimensions (and possibly effectively endless, where one could perish (“die”) merely exploring one tricky branch). some hard open problems might yield with more large scale/ organized/ systematic attacks, that is my personal belief.
  • despite very large bodies of historical research & results on them, it seems very few people worldwide are actively/ directly working on them at any one moment, and those that are dont network much with each other. still looking for a cyber-collaborative framework that would increase this focus/ leverage, think it is quite possible and hasnt been invented yet. stackexchange comes close in some ways (such as tags for questions/ answers relating to these key problems) but in other ways it fails. arxiv is another key resource of course. blogs are another. maybe a (scientific) blog registry by topic would help…?
  • the collatz problem is indeed amenable to a new approach not explored much elsewhere. combining a new/ unique fusion of algorithmics, datamining, hacking, empirical analysis, statistics, rapid prototyping, computational experimental, big data techniques. ofc all these separately have been around a long time but the combination/ gestalt is novel. the techniques are also quite similar to SAT transition point analysis found in the literature and Collatz amazingly even has similar thermodynamic-like properties such as transition point phenomena. unfortunately a lot of theoretical computer scientists do not seem to be aware/ value/ pursue this area much. it seems not mainstream (both empirical SAT research and appreciation of (power of) CS empirical approaches).
  • many new properties not published elsewhere have been discovered here. have been building on them. some seem disconnected but others are connected. exploring the dimensions of a single property leads to increased personal interest, drive, enthusiasm & momentum on the problem.
  • tying all the massive, diverse, somewhat seemingly disconnected properties of collatz into an overall coherent picture/ gestalt/ proof seems nearly impossible. some of the time it seems that none of the properties actually point in the direction of a possible proof. on the other hand this is part of the astonishing, unexpected, unintuitive complexity of the problem. its like an entire universe or set of universes in a tiny box/ packaging. it seems to be even more complicated than some fractals. (pandoras box, not yet opened, or maybe half opened?)
  • unfortunately there is overall little reaction elsewhere to this major attack on the problem despite very thorough publicizing attempts eg on other blogs (some high profile), stackexchange, reddit, etc., so a very high level of self-motivation has been required. its been not hard to engage with other enthusiasts on a somewhat superficial level, but not in a deeper/ more meaningful way. (cyber-) collaborative projects are very hard to build out of what might be called “natural or free motivation”. prizes/ grants would help in this area.
  • there are easily enough new minor-to-striking results here to justify/ comprise a paper at roughly the masters or even verging on the Phd level. publishing it on arxiv might lead to some attention, but overall doubt it would change the publicity equation that much, ie would it get much more attention than blog hits its already attained?
  • there have been a few minor but notable responses eg the stackexchange codegolf ripples, some expressions of interest in se chat rooms, etc.; the blog publicity has been as much an experiment in the social scientific realm as the computer experiments are in the math/ algorithmic realm.
  • there is not a single comment by any major authorities into these problems (eg collatz or P vs NP) in this blog, despite great hit counts, and that is a major disappointment and failure wrt early/ initial/ original intentions. on the other hand, it appears that major authorities rarely comment on blogs, even among some few who have blogs themselves. (which reminds me of this phd comic recently cited on physics se chat room, “average time spent composing one email.”) and its rare to get much comments from anyone. but these are aspects quite ubiquitous among blogging now as the massive potential audience seems to be spread almost infinitesimally thin (now among millions of blogs) in the long/well-known “long tail” phenomenon. these seem to be related to “scalability of social networking”. so maybe facebook is the answer? 🙄
  • since the blog was started and early experiments, there has been an increasing scientific confirmation of the general ideas linking collatz analysis to cutting edge research in undecidability and theorem-proving. this is something of a vindication. of course all this dates to an early proof by Conway linking them, but scientific research continues in this area. a special resonance can be seen in some writings of Michel.
  • there is some real pleasure on working on this extraordinarily deep, twisty, interdisciplinary, cutting-edge problem regardless of payoff and being able to find original insights/ real distinctive/ creative contributions. my intuition has long/ always been its the tip of a very big iceberg or rosetta stone. most scientific research can take many years of background/ historical study/ training to even begin to make a dent, yet number theory is a great field for dedicated outsiders eg as in the recent historic case of Zhang, and the odds/ risk of inadvertently duplicating others work is generally minimal. even simple tools like ruby + gnuplot can go a very long way.
  • long thought & fantasized about new software/ tools based on advanced CS/ math theory evolving/ materializing that could aid in attacking the problem. AT&T FSM library & graphviz are great and come close but both are over a decade old & while valuable turn out not to add much serious leverage so far. what about advanced algebraic automata theory constructions from decades old papers, where is the code for those? it looks like such tools are not anywhere on the horizon. and right now dont have other ideas for general tools myself either 😦

💡 ❗ ❓ an abstract/ general framework/ paradigm/ idea/ conjecture/ insight for a proof structure: global vs local

(4/6) an idea that seemed very interesting/ promising was to reformulate the problem in terms of/a pov that allows an algorithm to “make distinct choices” in deciding how to “resolve” trajectories. the 1st simple idea along these lines posted on codegolf stackexchange is to look at “blockwise trajectories” of consecutively starting seeds and allow the algorithm to choose which trajectory to advance next, and the algorithm would attempt to resolve all the trajectories in some streamlined/ balanced/ smooth way.

this leads to some other ideas & maybe a general way to conceptualize the overall problem as follows. an algorithm that can “look ahead” in a sense and see how a trajectory behaves in deciding how to traverse it can then better balance the choices.

in other words there seems to be a “global” versus a “local” aspect to this particular overall strategy. an algorithm with a global view can much better, or even nearly perfectly, balance the trajectory traversals. an algorithm that only can look “locally” at immediate information, such as current trajectory values, is more limited and will generally do worse in balancing its choices.

to further draw out this dichotomy, global metrics have an uncertain computational cost. they could take any amount of calculations, in a diverging rather than converging way (ie unbounded). local computations are more likely to be bounded.

so here is the idea that maybe the solution to the problem is in a sense “connecting the local to the global”. a nearly perfect global algorithm can be devised, then the trick is showing how an algorithm that can only access local computations can very nearly approach the same performance as the globally balanced algorithm. so then the question is, how much of the global structure of the problem is reflected in locally computed metrics? can the algorithm substitute global metrics with local ones without loss of performance? this then is also another way of looking at self-similarity as with fractals.

so aka that old expression “think globally, act locally”.

(4/8) 😳 ❗ 💡 ❓ this is some rather tricky code based on a surprising discovery, or a combination of 2. oops! the split functions are not working as intended to calculate lengths of 0-runs and 1-runs. the original intention was logic represented by the regexp /0+/ and /1+/ ie 1-digit-or-longer run delimiters. the actual ruby splitter logic triggered instead is a bit funky and hard to describe. (in short it is splitting empty strings separated by single delimiters, but not exactly.) rather than try to explain it exactly, wrote some code to simulate it and check that it matches.

but all this was discovered in analyzing a particular metric that has been graphed previously related to the unintended run parsing metric. that metric was just discovered to have a remarkable property that tracking its “running min value” matched closely with the initial glide for long glides.

this was graphed using gnuplot commands as follows for dual-axes plot (ofc found on stackoverflow via google). should have figured that out a long time ago, it comes in handy!

the blue line is the trajectory and the red/ green lines are a “running min value” on both the trajectory and the “funky” run length metric and nearly perfectly coincide. this is begging for a lot of further analysis but for now am posting these strange preliminary notes. the 2nd graph is the straight/ metric unpostprocessed (by the running min value).

set y2tics autofreq tc lt 3
plot 'out.txt' using 5 with line,'out.txt' using 4  with line, 'out.txt' using 2 with line axes x1y2
def stat(l)
        return 0, 0 if (l.empty?)
        t = t2 = 0
        l.each \
        {
            |x|
            t += x
            t2 += x ** 2
        }
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)
        raise if (sd.nan?)
        return a, sd
end
   
def dense(n)
  
        s = n.to_s(2)
        c = 0
        s.length.times \
        {
                |i|
                c += s[i, 1].to_i
        }
        return c.to_f / s.length
  
end

def f(n)

	n1 = n
	c = 0
	while (n != 1 && n >= n1)
		n = n * 3 + 1 if (n.odd?)
		n /= 2 if (n.even?)
		c += 1
	end
	return {'c' => c, 'd' => (0.5 - dense(n1)).abs}

end

def fmt(n)
	sprintf("%.03f", n)
end

def delim(s2)
	
	i = 0
	while (i < s2.length - 1)
		if (s2[i..i] != s2[(i + 1)..(i + 1)]) then
			s2[i + 1, 0] = '-'
			i += 1
		end
		i += 1
	end
	return s2
	
end

def sim(s, c)
	l = []
	l2 = s.split('-')
	l2.pop if (l2[-1][0..0] == c)
	l2.each \
	{
		|x|
		l += ((x[0..0] != c) ? [x] : ([""] * (x.length - 1)))
	}
	return l
end

def f2(n)

	n1 = n
	x = 0
	a = nil
	n2 = nil
	while (n != 1)
		x += 1
		n = n * 3 + 1 if (n.odd?)
		n /= 2 if (n.even?)
		
		s = n.to_s(2)
		l1 = (l1x = s.split('0')).map { |x| x.length }
		l2 = (l2x = s.split('1')).map { |x| x.length }
		
		a2, sd2 = stat(l1 + l2)

		if (a.nil? || a2 < a) then
			y = x
			a = a2
		end
		n1 = Math.log(n)
		if (n2.nil? || n1 < n2) then
			y2 = x
			n2 = n1
		end
		s2 = delim(s.dup)
		
		l1y = sim(s2, '0')
		if (l1x != l1y) then
			p(l1x)
			p(s2)
			p(l1y)
			raise
		end
				
		puts([x, fmt(n1), fmt(a2), y, y2].join("\t"))
	end
	
end


l = [{'n' => 1, 'p' => 0}.merge(f(1))]
t = 0

loop \
{
	l = l.sort_by { |x| [x['c'], -x['d']] }.reverse

	x = l.delete_at(rand([l.size, 2].min))

#	puts([t, x['c'], x['n'].to_s(2).length, x['p'], x['d']].join("\t"))
	
	p2 = x['p'] + 1
	n2 = x['n'] + 2 ** p2
	
	
	x1 = x.dup
	x1['p'] = p2
	l << x1
	
	x2 = {'n' => n2, 'p' => p2}.merge(f(n2))
	l << x2
	t += 1

	break if (t >= 500)
}

a = {}

l.sort_by { |x| -x['c'] }.each \
{
	|x|
	next if (a.member?(x['c']))
	a[x['c']] = x
	break if (a.size == 3)
}

f2(a.values[0]['n'])

long10

long10x

(4/10) this is some tricky/ tedious/ timeconsumingly debugged code which computes the unintended metric from the actual bit string lengths instead of from the empty-string splitting, and shows the equivalence of the two (it should not fail any tests ie raise any exceptions while running). after quite a bit of analysis to track down loose ends the mini-mystery is finally solved as revealed in this code with some approximations and algebraic transformations. the unintended metric is simply nearly tracking the iterate bit string length.

some consolation, at least some real closure here. had a feeling from begininning this might be the case. but had to look into this carefully & go thru the whole exercise for closure & in case it really was some independent way of tracking glides & running minima which would have been very important if real. (anyway, sigh… “back to the drawing board”… & this can be seen as just consequences/ karma for playing a bit fast & loose, getting carried away, ignoring some signs, banging with a hammer everything like a nail, & not validating/ testing the early metric formulations/ calculations carefully! live and learn!)

def stat(l)
        return 0, 0 if (l.empty?)
        t = t2 = 0
        l.each \
        {
            |x|
            t += x
            t2 += x ** 2
        }
        c = l.size
        a = t.to_f / c
        z = t2.to_f / c - a ** 2
        sd = Math.sqrt(z < 0 ? 0 : z)
        raise if (sd.nan?)
        return a, sd
end
   
def dense(n)
  
        s = n.to_s(2)
        c = 0
        s.length.times \
        {
                |i|
                c += s[i, 1].to_i
        }
        return c.to_f / s.length
  
end

def f(n)

	n1 = n
	c = 0
	while (n != 1 && n >= n1)
		n = n * 3 + 1 if (n.odd?)
		n /= 2 if (n.even?)
		c += 1
	end
	return {'c' => c, 'd' => (0.5 - dense(n1)).abs}

end

def fmt(n)
	sprintf("%.03f", n)
end

def delim(s2)
	
	i = 0
	while (i < s2.length - 1)
		if (s2[i..i] != s2[(i + 1)..(i + 1)]) then
			s2[i + 1, 0] = '-'
			i += 1
		end
		i += 1
	end
	return s2
	
end

def sim(s, c)
	s = '1' + s if (c == '1')
	l = []
	l2 = s.split('-')
	l2.pop if (l2[-1][0..0] == c)
	l2.each \
	{
		|x|
		l += ((x[0..0] != c) ? [x] : ([""] * (x.length - 1)))
	}
	return l
end

def sim2b(s, c)
	s = '1' + s if (c == '1')
	l = []
	l2 = s.split('-')
	l2.pop if (l2[-1][0..0] == c)
	l2.each \
	{
		|x|
		l += ((x[0..0] != c) ? [x] : ([""] * (x.length - 1)))
	}
	return l
end

def sum(l)
	t = 0
	l.each { |x| t += x}
	return t
end

def f2(n)

	n1 = n
	x = 0
	a = nil
	n2 = nil
	a3m = nil
	while (n != 1)
		x += 1
		n = n * 3 + 1 if (n.odd?)
		n /= 2 if (n.even?)
		
		s = n.to_s(2)
		l1 = (l1x = s.split('0')).map { |x| x.length }
		l2 = (l2x = s.split('1')).map { |x| x.length }
		
		a2, sd2 = stat(l1 + l2)

		if (a.nil? || a2 < a) then
			y = x
			a = a2
		end
		n1 = Math.log(n)
		if (n2.nil? || n1 < n2) then
			y2 = x
			n2 = n1
		end
		s2 = delim(s.dup)
		
		l1y = sim(s2, '0')
		l2y = sim(s2, '1')
		if ((l1x + l2x) != (l1y + l2y)) then
			p(l1x)
			p(l1y)
			p(l2x)
			p(l2y)
			raise
		end

		t1 = l1.size + l2.size
		l1z = s.split(/0+/)
		l2z = s.split(/1+/)[1..-1]
		
		c1 = l1.select { |x| x == 0 }.size
		l2z = [] if (l2z.nil?) 
		
		l2z2 = l2z.dup
		l2z2.pop if (s[-1..-1] == '0')
		c2 = sum(l2z2.map { |x| x.length - 1 })
		
		raise if (c1 != c2)
		
		c3 = l1.select { |x| x != 0 }.size
		c4 = l1z.size
		
		raise if (c3 != c4)
	
		
		c5 = l2.select { |x| x == 0 }.size
		l1z2 = l1z.dup
		l1z2.pop if (s[-1..-1] == '1')
		c6 = sum(l1z2.map { |x| x.length - 1 }) + 1
		c6 = 0 if (l1z2.empty?)
		
		raise if (c5 != c6) 
		
		c7 = l2.select { |x| x != 0 }.size
		c8 = l2z.size
		
		raise if (c7 != c8)
				
		a1 = sum((l1z + l2z).map { |x| x.length }).to_f / (l1z.size + l2z.size + c2 + c6)

		raise if (a2 != a1)
		
		c = sum((l1z + l2z).map { |x| x.length }).to_f
		
		a3x = c / (l1z.size + l2z.size + sum((l1z + l2z).map { |x| x.length - 1}) + 1)
		a3y = c / (l1z.size + l2z.size + sum((l1z + l2z).map { |x| x.length }) - (l1z.size + l2z.size) + 1)
		
		raise if (a3x != a3y)
		
		a3z = c / (c + 1)
		raise if (a3z != a3y)
		
		a3 = s.length.to_f / (s.length + 1)
		raise if (a3 != a3z)

		if (a3m.nil? || a3 < a3m) then
			y3 = x
			a3m = a3
		end
		
		puts([x, fmt(n1), fmt(a2), fmt(a3), y, y2, y3].join("\t"))
	end
	
end


l = [{'n' => 1, 'p' => 0}.merge(f(1))]
t = 0

loop \
{
	l = l.sort_by { |x| [x['c'], -x['d']] }.reverse

	x = l.delete_at(rand([l.size, 2].min))

#	puts([t, x['c'], x['n'].to_s(2).length, x['p'], x['d']].join("\t"))
	
	p2 = x['p'] + 1
	n2 = x['n'] + 2 ** p2
	
	
	x1 = x.dup
	x1['p'] = p2
	l << x1
	
	x2 = {'n' => n2, 'p' => p2}.merge(f(n2))
	l << x2
	t += 1

	break if (t >= 500)
}

a = {}

l.sort_by { |x| -x['c'] }.each \
{
	|x|
	next if (a.member?(x['c']))
	a[x['c']] = x
	break if (a.size == 3)
}

f2(a.values[0]['n'])

Advertisements

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