[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

272.0. "A collection question" by HARE::STAN () Tue Apr 30 1985 17:13

Given a finite sequence of non-negative integers (a, b, c, ...)
one can define a collection process as follows:

	Find the first pair of consecutive terms y, x that are
	out of order (i.e. y>x), remove them from the sequence,
	and replace them by the three terms: x, y, z where
	z is obtained by concatenating together the binary
	representations of y and x (in that order).

The process terminates when the resulting sequence is in non-descending order.

For example:

(1, 0) => (0, 1, 10)

(1, 0, 0) => (0, 1, 10, 0) => (0, 1, 0, 10, 100) => (0, 0, 1, 10, 10, 100)

[All numbers are represented in binary.]

The question is this:

Does the collection process applied to (1, 0, 0, 0) ever terminate?

The process begins as follows:

(1, 0, 0, 0) => (0, 1, 10, 0, 0)
	     => (0, 1, 0, 10, 100, 0)
	     => (0, 0, 1, 10, 10, 100, 0)
	     => (0, 0, 1, 10, 10, 0, 100, 1000)
	     => (0, 0, 1, 10, 0, 10, 100, 100, 1000)
	     => (0, 0, 1, 0, 10, 100, 10, 100, 100, 1000)
	     => (0, 0, 0, 1, 10, 10, 100, 10, 100, 100, 1000)
	     => (0, 0, 0, 1, 10, 10, 10, 100, 10010, 100, 100, 1000)
	     => (0, 0, 0, 1, 10, 10, 10, 100, 100, 10010, 10010100, 100, 1000)
	     => etc.

Another question is:
Does the collection process applied to (1, 1, 1, 0) ever terminate?
T.RTitleUserPersonal
Name
DateLines
272.1METOO::YARBROUGHTue Apr 30 1985 17:333
Not soon, at any rate: in either case the cycle with 29 numbers in it
has one number of more than 32 bits in it, so one can no longer check the
arithmetic with VAX longwords. - Lynn
272.2METOO::YARBROUGHTue Apr 30 1985 17:514
Even less likely. I looked at the case where (if the strings got above 32
bits long) one only exchanges if the lengths of two adjacent numbers are
wrong, and it doesn't quit. I generated strings > 500 digits this way.
-Lynn
272.3HARE::STANTue Apr 30 1985 19:421
A proof that the process never ends would be neat.
272.4R2ME2::GILBERTSun May 26 1985 18:458
Of course it never terminates.  In your example:

(1, 0, 0, 0) => (0, 1, 10, 0, 0)
	     ...
	     => (0, 0, 0, 1, 10, 10, 10, 100, 10010, 100, 100, 1000)

Note the subsequence (10010, 100, 100, 1000) must also be collected,
and its similarity to the (1, 0, 0, 0) being collected.
272.5TURTLE::GILBERTFri Jun 07 1985 23:592
Can you define a different ordering function over the integers, and with 1>0,
so the collection process, when applied to (1,0,0,0) *does* terminate?