Collatz conjecture experiments

collatz_conjecturethis section contains some experiments on the collatz conjecture which has deep connections to TCS.[4][19] this is the nagging, taunting, ¾-century-unsolved problem for which Erdös semifamously said:

Mathematics is not yet ripe for such problems. —Erdös

also Terrence Tao immediately cites it when referring to “mathematical diseases”[9] and as “One of the most notorious problems in elementary mathematics that remains unsolved”.[7] he compares succeeding on such problems to “winning the lottery”. maybe apropriately, the following is a work-in-progress & admittedly sketchy.

:star: :star: :star:

my major unique homegrown angle into this is a sort of datamining/near-hacking approach of writing simple programs to transform the function in key ways. this has led to many different angles and visualizations on the problem and have many assorted blogs on this approach now over the past half year (2013). heres a neat new one just generated, surprisingly simple yet evocative (the general goal of such exercises). it outputs integers in reverse order starting from 2 in a breadth-first expansion of the graph (logarithmic y axis). a fractal pattern of traversing higher integers is quite evident. (cant you just see the inductive proof leaping out at you?) :grin:

backward

l = [2]

seen = {}
30.times \
{
	l2 = []
	l.each \
	{
		|x|
		l1 = [x * 2]
		l1 << (x - 1) / 3 if (x % 3 == 1)
		l1.each \
		{
			|x2|
			next if (seen.member?(x2))
			seen[x2] = nil
			l2 << x2
		}
	}
	l = l2
	l2.each { |x| p(x) }
}

a remarkable correlation is that the following program which uses a real PRNG instead and a very slight alteration in logic to generate a very similar diagram, nearly visually indistinguishable, thereby emphasizing the connection of the algorithm to PRNGs.

backward3

l = [2]

srand

seen = {}
34.times \
{
	l2 = []
	l.each \
	{
		|x|
		l1 = [x * 2]
		l1 << x / 3 if (rand(3) == 0)
		l1.each \
		{
			|x2|
			next if (seen.member?(x2))
			seen[x2] = nil
			l2 << x2
		}
	}
	l = l2
	l2.each { |x| p(x) }
}

heres another simple program that produces interesting/remarkable/fractal-looking results. it simply enumerates in reverse order in a breadth-first fashion starting at 1 in this case for 42 levels of “breadth”, with the y coordinate the level associated with the x coordinate point.

image


l = [1]
seen = {}

42.times \
{
        |i|
        l2 = []
        l.each \
        {
                |x|
                l3 = []
                l3 << x * 2
                l3 << (x - 1) / 3 if (x % 3 == 1)
                l3.each \
                {
                        |x2|
                        next if (seen.member?(x2))
                        seen[x2] = i
                        l2 << x2
                }
        }
        l = l2
}

seen.keys.sort.each \
{
        |i|
        puts([i, seen[i]].join("\t"))
}

here is a slight modification of the prior algorithm that draws connections/lines between the levels and is reminiscent of the concept of tilings. (the first is exactly as discovered, a second version of the code is similar but conceptually simpler without the postprocessing logic/loop.)

image

l = [1]
seen = {}

40.times \
{
        |i|
        l2 = []
        l.each \
        {
                |x|
                l3 = []
                l3 << x * 2
                l3 << (x - 1) / 3 if (x > 1 && x % 3 == 1)
                l3.each \
                {
                        |x2|
                        next if (seen.member?(x2))
                        seen[x2] = [x, i]
                        l2 << x2
                }
        }
        l = l2
}

seen.each \
{
        |x2, xi|
        x, i = xi

        puts([Math.log(x), i].join("\t"))
        puts([Math.log(x2), i + 1].join("\t"))
        puts
}
l = [1]
seen = {}
 
40.times \
{
	|i|
	l2 = []
	l.each \
	{
		|x|
		l3 = []
		l3 << x * 2
		l3 << (x - 1) / 3 if (x > 1 && x % 3 == 1)
		l3.each \
		{
			|x2|
			puts([Math.log(x), i].join("\t"))
			puts([Math.log(x2), i+1].join("\t"));
			puts

			next if (seen.member?(x2)) 

			seen[x2] = nil

			l2 << x2
		}
	}
	l = l2
}

the following figures reveal the remarkable dichotomy of order and chaos in this visualization strategy. the above plots can barely look more ordered. however zooming in on the crosses/junctions/intersections of the lines reveals a chaotic pattern reminiscent of the rings of saturn (note these plots were generated by slightly different code):

cross_detail cross_detail

the earlier diagram showed how similar the collatz problem is to a PRNG (pseudo random number generator). this following concept expands on this from another angle. one might wonder if any program with random-looking output similar to the collatz trajectories could visit all integers. this is answered in the affirmative with this basic idea. start with an array of integers 1...n. then move an expanding window “leftward to rightward”. shuffle the elements of the array within the window each time. then output integers that are to the left of the sliding array (and are therefore not scrambled further). what does that look like? the result is not so dissimilar to some Collatz outputs that go in reverse order starting from 1 and output visited integers. but this also again shows how much the proof of the Collatz conjecture would seem to be similar to breaking a PRNG (which deterministically controls the scrambling). in the following n=500 and the highest index of the array output is about ~250. (the algorithm generalizes to arbitrarily large n.) in other words the diagram probably contains exactly once every integer n < \sim250 — exercise: why not surely?

scramble

c = 500
l = (1..c).to_a

n = 0
m = 5

while (n + m <= l.size)
	
	
	l2 = l[n, m]
	l[n, m] = []
	
	l2.shuffle!
	
	l[n, 0] = l2
	
	p(l[n])
	
	n += 1
	m += 1
		
end

:star: :star: :star:

the other approach Ive followed for many years is to construct a FSM transducer for iterations as described on the wikipedia page, “as an abstract machine that computes in base 2″ [3] although the origination of the technique is not so clear.[5] the FSM transducer computes iterates. built the transducer in the mid 1990s along with various auxiliary tools mainly for FSM logic. in the early ~2000s used the AT&T FSM library in many ways with this unique formulation.[6]

this approach has some strong connections to Shallit & Wilson [1] and is also similar to [2].

via this angle have found various interesting properties that probably have not been explored in the literature [which is large & forbidding, see eg the excellent survey/bibliography by Lagarias cited in [5]]. however, a proof is still elusive.

the general idea was/is to do a kind of experimental/empirical “datamining” on the algorithmic innards of the problem. this has led to many different views/angles/perspectives/analyses of the problem but (surprise!) not to a breakthrough so far.

fsm3nb.txt
this is the Collatz FSM iterate transducer. the s_{from} and s_{to} (state-from, state-to) are given in the 1st and 2nd column. the 3rd column is the input digit. the 4th column is the output digit. a 0 in the input or output column indicates \epsilon ie the empty string. the transducer computes iterates of the Collatz problem in binary, specified in lsb to msb order (least significant to most significant bit). binary digits are specified as pairs. the pair 11 indicates binary bit 0 and 12 indicates bit 1. the input number is terminated with the digit 2 in the first position. the final/end state is 30 with no new state, input, or output.
tree5.rb
this generates what might be called the “collatz graph”. the graph is all integers processed by the transducer working in series, like a “sandwich”. this graph can be explored in different orders. the general idea is that a particular enumeration order might lead to more insight or some kind of regular (as opposed to quasirandom) structure that would be amenable to induction.[8] there are currently two sort orders specified, rank1 and rank2 which are switched in the rank function. the code outputs the current iteration related statistics like the size of the graph. the prior and new graph nodes codes generated are output.
tree3b.rb
this code enumerates integers in a greedy order based on the size of the ensuing transducer sequence, but without the terminating ’1′ symbol that triggers the cascading final computation, which leads to a “cocked” transducer sequence/array (and also a natural equivalence class structure for assigning/sorting integers into). it also alternatively calculates the transducer array sequence via a recursive or fractal-like formula, and then verifies they are equal.

:star: :star: :star:

have many ideas on this problem & am more motivated to go into more detail with an engaged/interactive audience. therefore if you have any interest, reactions, or questions, please comment & it will help inspire me to continue to improve the detail of the writeup(s). note [22] is the link to lots more blog entries on the subj.

at times it feels a breakthrough is in the midst, within nearby reach, other times it all feels like a hopeless mirage not achievable in a single lifetime (there is some circumstantial evidence the problem may be undecidable, see eg [4]).

however do want to say one hopeful thing—have long strongly suspected that this problem may be resolvable with not-too-complex TCS that can not be easily/readily formulated in mathematical theory eg number theory, and the refs here would tend to support that and point in that direction.

selected refs

note: complete ref [1] is

Jeffrey O. Shallit and David W. Wilson (1991), The “3x + 1” Problem and Finite Automata, Bulletin of the EATCS (European Association for Theoretical Computer Science), No. 46, 1991, pp. 182–185.

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