collatz freaky alien landscape

❗ 💡 ❓ wow, this showed up while finally researching into graph centers using an algorithm suggested/ recommended by suresh, an idea that occurred to me over ½ year ago and finally got around to coding it recently (after realizing a fairly good greedy algorithm was quite easy to implement and runs quickly… its actually quite conceptually similar to Minimum Spanning Tree one of my favorite algorithms). the graph centers idea was intriguing and seems to work well in finding “few” graph centers that “cover” (via “intermediate hubs”) “blockwise-pieces” of the collatz graph. after looking at it, it was noisy but was also hard to even see an upward trend in number of graph centers required for the higher blockwise-pieces. (need to write this up at some point; am going to just append the undocumented code for the last version below for now).

so started looking at very high ranges of blockwise-piece graphs in the range starting at say 2^n, n>50, and this led to some rather shocking results. decided to just look at the size of the blockwise-piece graphs and compare it to the graph center “covers”…

then, threw away the graph centers idea entirely after the astonishing finding that the blockwise-piece graphs seem to converge somehow to constants as far as total # of vertices in the graphs. conjecture: maybe the graphs are isomorphic, the same graph?!? it should be easy to figure this out soon, but decided to dash off this intermediate result that looks at the convergence to constant-size blockwise-piece graphs for high n. on early analysis this looks really remarkable and maybe quite “exploitable.”

need to write all this up in more detail but for now hopefully the images and code is worth a few thousand words at least. this graph took over ~90m to generate on an 8 core intel i7-3720QM 2.6GHz. the code has 3 separate graph modes and it was found they are all more-or-less related wrt this “constant-converging” property, but the “mode 2” graph has the smallest size.

big2y

big2x

def f(n, w = nil)

	n1 = n
	while (n >= n1)

		case w
			when 1
				n2 = n.even? ? n / 2 : (n * 3 + 1)
			when 2
				n2 = (n * 3 + 1) / 2 if (n.odd?)
				n2 /= 2 while (n2.even?)
			else
				n2 = n.even? ? n / 2 : (n * 3 + 1) / 2
		end

		$g[n] = {} if (!$g.member?(n))

		break if ($g[n].member?(n2))

		n2 = 1 if (n2 < n1)
		$g[n][n2] = nil
		$g[n2] = {} if (!$g.member?(n2))
		$g[n2][n] = nil
		n = n2
	end

end

def g(m0, m1, w = nil)

	$g = {}

	n = m0
	while (n < m1)
		f(n, w)

		n += 2
	end
	return $g.keys.sort

end

def sample(x, d)

	l = []

	(20..100).each \
	{
		|n|

		m0 = 2 ** n + 1 + x
		m1 = m0 + x + d

		l << g(m0, m1, 2).size
	}

	l.pop while (l[-1] == l[-2])
	return l.size

end

def delta(w, c)

	(1..c).to_a.map { |x| (x.to_f / c * w).to_i }

end

f = File.open("out.txt", 'w')

delta(15000, 20).each \
{
	|x|
	l = []
	delta(15000, 20).each \
	{
		|d|
		l << sample(x, d)
	}
	s = l.join(" ")
	puts(s)
	f.puts(s)
	f.flush
}

f.close

 

def f(n)

	n1 = n
	while (n >= n1)
		n2 = n.even? ? n / 2 : (n * 3 + 1) / 2

		$g[n] = {} if (!$g.member?(n))

		break if ($g[n].member?(n2))

		n2 = 1 if (n2 < n1)
		$g[n][n2] = nil
		$g[n2] = {} if (!$g.member?(n2))
		$g[n2][n] = nil
		n = n2
	end

end

def centers(m0, m1, m2)

	$g = {}

	n = m0
	while (n < m1)
		f(n)

		n += 2
	end

	v = $g.keys
	l = [v[rand(v.size)]]

	d = {}
	l1 = []

	loop \
	{

		v1 = v.dup
		c = 0

		while (!l.empty?)
			l2 = []
			while (!l.empty?)

				a = l.shift
				next if (!d[a].nil? && d[a] < c)
				d[a] = c
				v1.delete(a)
				l2 += $g[a].keys & v1

			end
			c += 1
			l = l2
		end

		z = d.max_by { |x, y| y }
		l1 << z[0]
		break if (z[1] <= m2)
		l = [z[0]]
	}
	return l1, v.size

end

t = Time.now.to_i
f=File.open('out2.txt', 'w')

h = {}
500.times \
{
	|j|
	l, n = centers(j * 500 + 1, (j + 1) * 500, 25)
	p([j, l.size, n])
	f.puts([l.size, n].join("\t"))
	f.flush
}
f.close

printf("%.2fm\n", (Time.now.to_i - t) / 60.0)

(8/15) @#%& wordpress changed their editor within last few days and it has a glitch that messes up code samples on the 2nd save of the post, as far as html character substitutions. geez! (have probably seen this before maybe with the ipad app also.) they reenabled the “classic” editor with a link today so am adding some new code finally. this is some more code that shows that this constant property happens for blockwise pieces starting at powers of “multiples of” 2; it shows up for powers of 2, 6, 10 but not seen yet for powers of 3, 5, 7. this is obscured somewhat by the default color selection on the large graph but the detail/zoom shows this better. the gnuplot graph was a real hassle to find the right commands to support a black background. gnuplot is both simultaneously very powerful and a hassle to do some basic changes at times! took a lot of searching to find hack-like cmds that work! including the gnuplot code.

big4cx

big4cy

def f(n, w = nil)

	n1 = n
	l = [n]
	while (n >= n1)

		case w
			when 1
				n2 = n.even? ? n / 2 : (n * 3 + 1)
			when 2
				n2 = (n * 3 + 1) / 2 if (n.odd?)
				n2 /= 2 while (n2.even?)
			else
				n2 = n.even? ? n / 2 : (n * 3 + 1) / 2
		end

		$g[n] = {} if (!$g.member?(n))

		l << n2 if (n2 != 1)
		break if ($g[n].member?(n2))

		n2 = 1 if (n2 < n1)
		$g[n][n2] = nil
		$g[n2] = {} if (!$g.member?(n2))
		$g[n2][n] = nil
		n = n2
	end
	$l << l
end

def g(m0, m1, w = nil)

	$g = {}
	$l = []

	n = m0
	while (n < m1)
		f(n, w)

		n += 2
	end
	return $g.keys.sort

end

def sample(x, d)

	$a = {}
	$b = {}

	l = []
	(0..250).each \
	{
		|n|

		m0 = x + (d * n)
		m0 += 1 if (m0.even?)
		m1 = m0 + d
		c = g(m0, m1, 2).size
		l << c
	}
	t = 0
	l.each { |x| t += x }
	return t.to_f / l.size
end

200.times \
{
	|z|
	l = []
	[2, 3, 5, 6, 7, 10].each \
	{
		|n|
		l << sample(n ** (z + 1), 500)
	}
	puts(([z] + l).join("\t"))
	$stdout.flush
}
set object 1 rectangle from screen 0,0 to screen 1,1 fillcolor rgb "black" behind
set tics textcolor rgb "gray"
set border lc rgb "gray"
set key tc rgb 'gray'

recursive binary fall-below suffixes

(8/22) the actual property involved seems to be related to that explored earlier where “base 2 non-fall-below suffixes” can be generated. here is some slight variation on that prior code and which also generates the set recursively. looking into good ways to visualize this. output run for arg “8”.

def check(n, b)

	a = n
	b0 = b
        while (a >= n) 

            if (b.odd?) then
		a *= 3
		b = b * 3 + 1
            end
		if (b.even?) then
			return [b0] if (!a.even?)
			a /= 2
			b /= 2
		end
	end

	return []

end

def scan(p)

    n = 2**p
    l = []

    (1...n).each \
    {
        |i|

	l += check(n, i)

        a = n
        b = i
     }

	return l
end

def recur(n)

	l = [1]

	(2..n).each \
	{
		|p|
		l2 = []
		l.each \
		{
			|x|
			l2 += check(2 ** p, x)
			l2 += check(2 ** p, x + (2 ** (p - 1)))
		}
		l = l2
	}
	return l
end

def out(l, n)
	l.sort.each { |x| printf("%0#{n}d\n", x.to_s(2)) }
end

n = ARGV[0].to_i

l1 = scan(n)
l2 = recur(n)

puts(l1.sort == l2.sort)

out(l2, n)
true
00011011
00011111
00101111
00111111
01000111
01011011
01100111
01101111
01111111
10011011
10011111
10100111
10111111
11001111
11011111
11100111
11101111
11111011
11111111

this is some neat code that uses the previous ideas that “long-not-fall-below” trajectories have easily computable base 2 suffixes to find “very large” trajectories using a greedy search and different metric/weight heuristics, ie more of a depth-first search than the prior breadth-first traversal.

(recently found a nice page on this cited by Lagarias by Eric Roosendaal with all kinds of numerical records, it calls this property the “glide” of a trajectory.)

this code seems quite notable in that it can find very long non-fall-below trajectories without much memory or computation via the recursive graph-traversing formula rather than an exhaustive search through the trajectory space. could it find record size “non fall below” trajectories based on amazingly improved efficiency? it does seem to easily outdo Roosendaals glide table record so maybe this algorithm is not previously discovered. output (# iterations, size of memory list, final large “non fall below” value):

[150, 129, 89568408267387035640032798643111999]
def count1(n)
	c = 0
	while (n != 1)
		c += 1 if (n.even?)
		n = n.even? ? n / 2 : n * 3 + 1
	end
	return c
end

def count2(n)
	c1 = 0
	c2 = 0
	while (n != 1)
		n.even? ? c1 += 1 : c2 += 1
		n = n.even? ? n / 2 : n * 3 + 1
	end
	return [c1, c2]
end

def count(p, b, b0, w)
	case w
		when '1'
			c1, c2 = count2(b0)
			return c1 + c2
		when '2'
			c1, c2 = count2(b0)
			return c2
		else
			return p + count1(b)
	end
end

def check(p, b, w)

	n = 2 ** p
	a = n
	b0 = b
        while (a >= n) 

		if (b.odd?) then
			a *= 3
			b = b * 3 + 1
		else
			return [[b0, count(p, b, b0, w), p + 1]] if (!a.even?)
			a /= 2
			b /= 2
		end
	end

	return []

end

def recur(n)

	l = [[1, 0, 2]]

	(2..n).each \
	{
		l2 = []
		l.each \
		{
			|x, c, p|
			l2 += check(p, x)
			l2 += check(p, x + (2 ** (p - 1)))
		}
		l = l2
	}
	return l
end

def recur2(n)

	l = [[1, 0, 2]]

	loop \
	{
		break if (l[0][2] > n)
		x, c, p = l.shift

		l += check(p, x)
		l += check(p, x + (2 ** (p - 1)))
	}

	return l
end

def recur3(w)

	l = [[1, 0, 2]]
	t = 0

	loop \
	{
		t += 1
		l.sort_by! { |x, c, p| -c }
		break if (t == 150)
		x, c, p = l.shift

		l += check(p, x, w)
		l += check(p, x + (2 ** (p - 1)), w)
	}
	p([t, l.size, l[0][0]])
	return l
end

w = ARGV[0]
l2 = recur3(w)

Advertisements

3 thoughts on “collatz freaky alien landscape

  1. Pingback: *** COLLATZ BREAKTHRU *** | Turing Machine

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

  3. Pingback: Speed test WAN(RX) with nice char – FAST & SHORT scripts and comands for Linux and…

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