❗ 💡 ❓ *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 , 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 . 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.

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.

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)

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

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