a new pair of collatz ideas & striking/promising new visualizations

hi all. some rough new ideas dashed off about collatz that have been bumping around in my head for awhile. [also fyi, small )( blogging joy/ victory, the last post on $3M breakthru prizes got the 2nd highest daily hits ever due mainly to reddit & Tao blog as referrers, and presumably the $$$ topic!] ❗ 😀 😎

my last post on collatz has mushroomed into a big grab bag/ kitchen sink of miscellaneous observations and code over several months of adding to it & shows some of the inherent messiness behind-the-scenes, such as once again tripping over the “seen cache” logic, which also showed up in the very 1st post on the subj on this blog. anyway further musing/ pondering on these leads to a few new ideas/ directions.

💡 idea 1

during investigation, have come up with a series of new algorithms that attack the problem from different angles. these lead naturally to multiple conjectures roughly in the form “if the collatz function conforms to this upper bound, then the collatz conjecture is true”. was pondering this scenario.

consider a bunch of TMs and inputs TM_1, TM_2, ... any of which if proven nonhalting would prove the collatz conjecture. another idea is to combine them all into a larger conjecture that all of them dont halt.

this reminds me (loosely) of a pattern that showed up during the netflix datamining contest that so far hasnt been widely publicized much. it involved finding a linear combination of many different peoples (contestants) solutions. every separate solution seemed to have a measure of linear independence from all the others. finding the optimal linear combination of independently-derived solutions improved substantially the overall combined solution.

how could this be applied to the collatz/halting problem? it seems that the only operation that can be done on a TM is “advance one step”. but came up with this interesting idea. consider a finite set of TMs and starting conditions. suppose that they are all nonhalting. how could one prove this? in such a way as combining them all into some solution?

my idea is that one could create an algorithm that chooses which of the TM_n to advance next, and that somehow via ingenuity in this algorithm, a pattern might emerge among the advancing TM_n that is not possible to extract in any individual TM_n but emerges with the whole set aka gestalt.

but then notice how remarkably similar this is to the last major idea posted here on collatz, namely that one can look at finite “bunches” or “blocks” of trajectories simultaneously, and decide which in the finite set to advance next.

looking this over, the two ideas between advancing TMs/collatz trajectory bunches are nearly the same idea.

also, its a more general strategy that transcends collatz and can apply to attacking undecidable problems in general esp via machine learning approaches. the machine learning algorithm attempts to make choices that “maximize the pattern/ order and decreases the randomness” of the TM advancings.

💡 idea 2

as for the last advancing bunch collatz trajectory idea, another interesting concept emerges. suppose that one wants to choose some subset of the bunch to advance simultaneously. from simulations, one wants to minimize the “size” of the total decremented trajectory sum, ie minimize the absolute delta value, but also keeping it negative. otherwise the algorithms are too “greedy” and decrease rapidly into local minima early and then get “bad” results later in the run eg/ie large random spikes etc. the “keeping it negative” condition during this minimization reflects that one does not want to exceed the current total trajectory sum (ie seeking an “orderly” monotonically decreasing path).

so then in other words (more formally) let S be a finite set of trajectories and d_s, s \in S are the current delta values. the problem is to minimize |D| where

D = \Sigma_{s \in S}\,d_s subject to D < 0

in other words D should closely approach 0 from the negative side but not exceed it. but notice how remarkably similar this is to the well known subset sum problem!

have not worked too much with the subset sum problem, but its neat that it shows up here because theres so much theory and code available on it. am feeling like it would be interesting to take an off-the-shelf solver and hook it up to the problem.

more news

have some neat new empirical/ visual findings about the randomness inherent in the so-called Collatz random walk. recently ran across some simple/neat ways to show that it lacks quite a bit of randomness and has basic mean-returning properties, which have been studied in fractal theory—one of them looking rather striking and promising. they look rather obvious in 2020 hindsight but yet seem fundamental.

so now consider again the “odd/even sequence” associated with each trajectory denoted as 0/1 strings. one can look at this from various angles. in an earlier post a lot of structure is demonstrated to exist in these sequences based on grammar decomposition. the 1st idea here is to start at sequential integers, and plot the odd even sequence as random walks where even integers add -1 to the walk and odd integers add +1 to the walk. not surprisingly this looks like an earlier plot, but it brings out better a remarkable detail. namely, the 0/1 sequences are far from a random walk, and exhibit mean-returning behavior, to the general trendline of more even occurrences (hence decreasing overall).

branch3b

def f(n)

	l = []
	while (n != 1)
		x = n.even?
		l << x
		n = x ? n / 2 : n * 3 + 1
	end
	return l

end

def out(x1, y1, x2, y2)
	l = [x1, y1, x2, y2]
	return if ($seen.member?(l))
	puts(l[0..1].join("\t"))
	puts(l[2..3].join("\t"))
	puts
	$seen[l] = nil
end

$seen = {}

n = 1
4000.times \
{

	l = f(n)

	y = 0
	l.each_with_index \
	{
		|f, x|

		x1, y1 = [x, y]
		y += (f ? -1 : 1)
		out(x1, y1, x + 1, y)
	}

	n += 2
}

using the same strategy one can map the “reverse tree” that “supposedly/possibly” visits all integers starting at 1, leading to a similar diagram which shows roughly the same phenomenon and again matches an earlier graph.

fork5b

def out(l)
	return if ($seen.member?(l))
	puts(l[0..1].join("\t"))
	puts(l[2..3].join("\t"))
	puts
	$seen[l] = nil
end

l = [[1, 1, '']]

c = 40
c.times \
{
	|x|
	l2 = []
	l.each \
	{
		|y1, y2, p|
		l2 << [y2, y2 * 2, p + '0']
		l2 << [y2, (y2 - 1) / 3, p + '1'] if (y2 != 1 && y2 % 3 == 1)
	}

#	l = l2
#	next

	l = []
	s = {}
	t = 0
	l2.each \
	{
		|y1, y2, p|
		next if (s.member?(y2))
		s[y2] = nil
		l << [y1, y2, p]
	}
}

$seen = {}

l.each \
{
	|y1, y2, p|
	t = 0
	p.split('').each_with_index \
	{
		|b, x|
		l = [x, t]
		t += (b == '1') ? 1 : -1
		out(l + [x + 1, t])
	}
}

these diagrams lead to a natural, amazing observation/conjecture. what kind of phenomena would give “somewhat” random walks that are “trendline-returning” and explain this? a simple idea is as follows. every time the line increments, increment an “up” counter. every time it decrements, increment the “down” counter. now if the (absolute) difference between the up and down counters is never large, one would expect trendline-returning behavior like as seen. so it is natural to then plot this quantity. but a small shock ensues, one finds that this max up/down counter difference is highly correlated with the total stopping time!

branch6

def f(n)

	a = 0
	b = 0
	m = 0
	c = 0
	while (n != 1)
		x = n.even?
		n = x ? n / 2 : n * 3 + 1

		if (x) then
			a += 1
		else
			b += 1
		end
		m = a - b if (a - b > m)
		c += 1
	end

	return [m, c]

end

n = 3
y = 0
2000.times \
{

	l = f(n)
	puts(l.join("\t"))
	n += 2
}

⭐ ⭐ ⭐

maximal edge trace, colored radial graphs

(7/21) returning to the earlier 1st graph, one sees that the “odd even sequence as semirandom walk” or “operation sequence line/walk” stays within a given “roughly linear” range. a natural idea is to look at the maximal “edge” of this line, ie the highest possible collatz sequences staying inside of the range. if it were decreasing that could be a real advance on the problem. this is not quite the same as looking at individual trajectory maximal “ceilings” (there is likely no actual single trajectory that entirely follows that edge, those that reach it only touch on it temporarily); its a sort of composite ceiling of worst case trajectory paths. and voila, one can see the mean-returning tendency of this new metric. here is a plot of this function for integers in the range [1000..39000] at increasing steps of 2000.

ceilingb


def f(n)

	x = 0
	y = 0
	l = [[x, y]]
	while (n != 1)
		f = n.even?
		n = f ? n / 2 : n * 3 + 1
		f ? x += 1 : y += 1
		l << [x, y]
	end

	return l

end

def out(l)

	(l.size - 1).times \
	{
		|x|
		puts((l[x] + l[x + 1]).join("\t"))
	}
	puts

end

20.times \
{
	|t|

	n = 3
	l2 = []

	(1000 + t * 2000).times \
	{

		l = f(n)
	#	out(l)
		l.each \
		{
			|x, y|
			l2[x] = y if (l2[x].nil? || y > l2[x])
		}
		n += 2
	}

	n = 1.0
	(l2.size - 1).times \
	{
		|i|
		n /= 2
		n = n * 3 + 1 if (l2[i] != l2[i + 1])
		puts([i, Math.log(n, 2)].join("\t"))
	}
	puts

}

(7/22) heres another idea whipped out on a whim. how does one visualize the collatz graph? as noted earlier jason davies has one of the best & most remarkable visualizations on the net. however heres another approach that looks at all the trajectories within powers of two, visualized on a circle graph. this really reminds me of watts/strogatz small world graph model. most edges are local and the graphs look somewhat “regular” except for occasional “tunneling” links that jump long distances. those are the powers of two or number with many even factors where large leaps can be made in a single sequence (they are combined in this code). the code without the leap logic leads to very regular looking circular graphs where all connections look local, there is little to look at. this is one of the rare color visualization on this site. color could definitely be used to more effect in some visualizations.

there are four separate graphs offset by a small distance, plotted on top of each other for all integers below 2^n, n \in [7..10] with the denser graphs plotted first and the sparser graphs plotted on top of them sequentially. another point is that in numerical experiments for all integers into the millions, it seems that the max integer occurring in the trajectory for integers within [1..2^n] is less than roughly 2^{2n}. these max integers are the lower extreme point of the “C” figures below (point with max radian, starting at 0 at (1,0) and rotating counterclockwise). alas, other than hint at small world structure, so far these graphs dont seem to lead somewhere other than re-emphasizing the heavily random nature of some views of the problem. as the expr goes (a verdict occasionally handed down witheringly/ ruthlessly by one of my managers from years ago) “off in the weeds”…!

circleb


d = 0.05
(7..10).each_with_index \
{
	|c, i|

	m1 = 2 ** c

	x = 3
	l = []
	while (x < m1)
		x1 = x

		while (x1 != 1)
			x2 = x1.even? ? x1 / 2 : (x1 * 3 + 1) / 2
			x2 /= 2 while (x2.even?)

			l << [Math.log(x1), Math.log(x2)]

			x1 = x2
		end
		l << nil
		x += 2

	end

	m = l.compact.flatten.max

	f = File.open("out#{c}.txt", 'w')

	l.each \
	{
		|a, b|
		if (a.nil?) then
			f.puts
			next
		end

		t1 = a / m * 2 * Math::PI
		t2 = b / m * 2 * Math::PI
		f.puts([Math.cos(t1) - i * d, Math.sin(t1), Math.cos(t2) - i * d, Math.sin(t2)].join("\t"))
	}
	f.close

}

(7/23) a natural idea is to renumber the radial position of vertices using some strategy. many obvious ones based on indegree, outdegree, or degree are possible. so far only the outdegree sort seems to organize/layout the graph better. the 2nd diagram uses a [outdegree, indegree] sort & seems to show some bipartite tendency of edges between top and bottom halves. (7/24) full disclosure, this has a silly defect in correctly initializing the trajectory.

circle2

circle2x

d = [[0, 2], [2, 2], [0, 0], [2, 0]]
c = 200

[5,6,7,8].each_with_index \
{
	|n, i|

	m1 = c * n + 1
	m2 = c * (n + 1)

	x = m1

	into = {}
	out = {}

	while (x < m2)

		x1 = x
		while (x1 != 1)
			x2 = (x1 * 3 + 1) / 2 if (x1.odd?)
			x2 /= 2 while (x2.even?)

			out[x1] = [] if (!out.member?(x1))
			out[x1] |= [x2]

			into[x2] = [] if (!into.member?(x2))
			into[x2] |= [x1]

			x1 = x2
		end
		x += 2

	end
	v = into.keys | out.keys
	j = {}

#	v.sort_by { |x| (out[x].nil? ? 0 : out[x].size) + (into[x].nil? ? 0 : into[x].size) }.each_with_index { |x, y| j[x] = y }
	v.sort_by { |x| out[x].nil? ? 0 : out[x].size }.each_with_index { |x, y| j[x] = y }
#	v.sort_by { |x| [out[x].nil? ? 0 : out[x].size, (into[x].nil? ? 0 : into[x].size)] }.each_with_index { |x, y| j[x] = y }
#	v.sort_by { |x| [into[x].nil? ? 0 : into[x].size, out[x].nil? ? 0 : out[x].size] }.each_with_index { |x, y| j[x] = y }

	f = File.open("out#{n}.txt", 'w')
	out.keys.each \
	{
		|v1|

		out[v1].each \
		{
			|v2|

			r1 = j[v1].to_f / v.size * 2 * Math::PI
			r2 = j[v2].to_f / v.size * 2 * Math::PI
			x1, y1 = [Math.cos(r1) + d[i][0], Math.sin(r1) + d[i][1]]
			x2, y2 = [Math.cos(r2) + d[i][0], Math.sin(r2) + d[i][1]]
			f.puts([x1, y1, x2, y2].join("\t"))
		}

	}
	f.close

}

💡 mining number theory for analogies

(7/24) have you ever seen basic plots of basic number theoretic properties? these graphs seem to be rarely generated or encountered. for quite awhile have been musing on possible analogs between the collatz problem and basic number theoretic areas. eg factoring and primes seem to have some of the same deterministic-yet-random aspects; this possiblity is strengthened by many parallels to ideal theory in many collatz analyses.

for example, just plotting the maximal prime in prime factorings of sequential integers leads to an interesting graph that is definitely reminiscent of earlier graphs encountered in processing collatz trajectories, 1st figure below, similar to [1][2]. (a big congratulations to anyone who can cite this graph in published literature!) also, just counting the number of prime factors of sequential numbers leads again to another similar-looking graph encountered on processing collatz trajectories, 2nd figure, similar to [3].

this all shows that even though collatz appears to be one of the ultimate cross cutting problems through many areas of math and computer science, its classification as a fundamentally number theoretic problem is highly justified. the weird hybrid/chimeric random vs deterministic qualities of number theory have been pondered for millenia, since the greeks… & for collatz, a youngster at only ~¾-century old, its also deja vu all over again.

factA

factB

def f(x)

	l = []
	n = 2

	while (n <= Math.sqrt(x))

		if (x % n == 0) then
			x /= n
			l << n
			next
		end

		n += (n == 2) ? 1 : 2
	end

	l << x if (x != 1)
	return l

end

(1..1000).each \
{
	|x|
	l = f(x).sort
	puts([l[0], l[-1], l.size].join("\t"))
}

more striking linear/ balance trends

(8/5) continuing the paradoxical properties, these graphs are both striking and not striking in the sense that they are so normal- and nonrandom- looking. this extends the earlier look at relations between the two operations. seems fundamental somehow and a big piece of the puzzle. the linear trend is so smooth! this shows a balance in the two operations over iterates in a range over two consecutive powers of 2. definitely needs further inquiry/ analysis! there seems to be a case of a 2d equivalence class concept here. many points are “sorting” into a fewer (2d) equivalence classes. looking at the output, often consecutive integers/ trajectories sort into the same classes! (this also ties in with the 7/18 post on the blog “collatz binary mappings similar to codes” about connections to codes and the C(x, y) function.)

hi4x

hi4y

def count(n)

	x = 0
	y = 0
	while (n > 1)

		n.even? ? x += 1 : y += 1
		n = n.even? ? n / 2 : n * 3 + 1
	end
	return [x, y]

end

def count2(n)

	x = 0
	y = 0
	while (n > 1)

		n.even? ? x += 1 : y += 1
		n = n.even? ? n / 2 : (n * 3 + 1) / 2
	end
	return [x, y]

end

j = 10

m1 = 2**j + 1
m2 = 2**(j + 1)

n = m1
l = []
while (n < m2)

	x, y = count(n)
	x2, y2 = count2(n)
	puts([n, x, y, x2, y2].join("\t"))

	n += 2
end

this next sequence a slight variation just plots sequential regions in different colors each with some small offset. from inspection the x-intercept is roughly/ simply the exponent on the power of two associated with the region.

hi4c


def count(n)

	x = 0
	y = 0
	while (n > 1)

		n.even? ? x += 1 : y += 1
		n = n.even? ? n / 2 : n * 3 + 1
	end
	return [x, y]

end

def count2(n)

	x = 0
	y = 0
	while (n > 1)

		n.even? ? x += 1 : y += 1
		n = n.even? ? n / 2 : (n * 3 + 1) / 2
	end
	return [x, y]

end

d= 4

(8..11).each \
{
	|j|

	m1 = 2**j + 1
	m2 = 2**(j + 1)

	f = File.open("out.#{j}", 'w')
	n = m1
	while (n < m2)

		x, y = count(n)
		x2, y2 = count2(n)
		f.puts([n, x + j*d, y, x2 + j*d, y2].join("\t"))

		n += 2
	end
	f.close
}

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