Conference rusure::math

Andy Strangeways' sundry sequence #4, from Note 886, is very relevant here.
Notes 14 & 42 talk about a different, and slightly related, problem.

Andrew.

    I conjecture that it works for any length sequence, but that it takes
    more iterations to settle down.  I could probably prove it, but I don't
    have the time right now.
    
    Dick

re .2
    
>    I conjecture that it works for any length sequence, but that it takes
>    more iterations to settle down. 
    
    Trying a case of length 3 shows that it doesn't always work for any
    length (assuming I didn't slip up).
    
    5    3    17
      2    14    12
        12    2     10
           10     8    2
               2    6    8
                  4    2    6
                     2    4    2
                        2    2   0
                          0   2   2
                           2   0   2
                            2   2   0
                             .........
                             .........
    
    P.S.
    
>     <<< Note 1658.2 by SGOUTL::BELDIN_R "D-Day: 212 days and counting" >>>
    
    So what happens in 212 days time?

	The key idea is given in John Munzer's 886.5.   (Whatever happened to
him, btw?   He's still in Elf...)   I've sent off a reply into Usenet, which
I'll copy into this Notesfile for those who use not usenet.

	Essentially, I argue that the sequence becomes a constant (wlog, 0) iff
its length is a power of 2.   I hope I'm not wrong!   I haven't sent a reply
into Usenet before.

	I raised a question in 886.11, about fixpoints in sequences of length
*not* a power of 2, which I alleged at the time to have solved.   I'm not sure
that I did solve it, but the problem is interesting, evoking the kind of issues
that come up in the easier case of Sundry Sequence #1 (see again 886.)

Cheers,
Andrew.

Article 6684 of rec.puzzles:
Newsgroups: rec.puzzles
Path: vbohub.vbo.dec.com!heron.enet.dec.com!buchanan
From: buchanan@heron.enet.dec.com (Andrew Buchanan)
Subject: Re: Four of a kind
Message-ID: <1992Aug31.134120.3539@vbohub.vbo.dec.com>
Keywords: puzzle
Lines: 63
Sender: usenet@vbohub.vbo.dec.com (USENET News System)
Nntp-Posting-Host: statos
Reply-To: buchanan@heron.enet.dec.com (Andrew Buchanan)
Organization: Digital Equipment Corporation
References:  <1992Aug27.183258.15169@ecst.csuchico.edu>
Date: Mon, 31 Aug 1992 13:41:20 GMT


In Article <1992Aug27.183258.15169@ecst.csuchico.edu>, 
PANDERSON@OAVAX.CSUCHICO.EDU (Peter Anderson) writes (modulo some minor 
syntactic slips I've taken the the liberty of correcting):

>Take four numbers and write them down beside each other. e.g.
>
>5   3   17   34
>
>Find the difference between each number and the number to its right. In 
>the case of the fourth number find the difference between it and the first 
>number( that is in this case between 34 and 5). Continue to do this and 
>you will always come to four of the same number.
>
>Example:
>
>5   3  17   34
>2   14  17  29
>12  3    12  27
>9   9     15  15
>0   6      0    6
>6   6      6    6
>
>This apparently only works with four numbers.
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

	Not so.

	Say the initial sequence, S, has length n.   Assume wlog that S has 
period n (ie, S is not just a repetition of some shorter subsequence).   Then
iteratively applying the function described, f, yields a constant value 
if n is a power of 2.   On the other hand, if n has an odd prime factor, then
there exists a sequence, S, of length n which never yields a constant value
under iterative application of f.


Sketch of Proof:

	Let S_0 = S.
	For j>=0, let S_j denote (f^j)(S) (ie, f iteratively applied j times to
S)
	Let r_j >= 0 denote the largest integer such that 2^(r_j) divides
every element of S_j.
	Let K_j >= 0 denote the largest member of S_j.

	Suppose first that n=2^m.
	Then simple consideration of Pascal's triangle mod 2^(r_0) shows that
r_(2^m) > r_0.   By repeating this, we see that r_(2^(mt)) -> infinity with t. 
Yet K_(2^mt)) < K_0.   Therefore, there exists j such that f^j(S) consists
entirely of zeros.

	Now suppose instead that n has an odd prime factor p.   Let S(i), the 
ith element of the sequence S, be given by: 
	S(i) = 2i + k(i mod p), 
where k is a function from {0,1...,p-1} to {0,1}, such that:
	|{x in {0,1,...,p-1}, k(x)=1}| is neither 0 nor p.
Then it's easy to see that S has period n, and r_t = 0 for all t.   This means
that no matter how many times f is applied to this S, we can never reach a
constant value.   Try it with the sequence 1,3,4 for instance.

Cheers,
Andrew.

>		What are the stable strings?				    
>									    
>   i.e. the strings based on the alphabet {0,1} that under the transformation 
>   we've been discussing remain 'unchanged'.   (Rotated, but not reversed)
>									     
>   e.g. 0 -> 0,    110 -> 110						     
>									     

	So, for instance:

	1 1 0
goes to:
	 0 1 1

which is just a rotation of the original string (which we can view as a cycle)

	We can parse any such cyclic string as alternate strings of 1's and 
strings of 0's.   Let f_i denote the number of 1-strings of length i, and let 
g_i denote the number of 0-strings of length i.

	So for instance, in the string 110 above, f_2 = g_1 = 1, and all other
values of f_i & g_i are zero.

	Then its a *necessary* condition for a stable string that:

	f_1 = sum(i>=3) (i-2)*f_i
	g_j = sum(i>j) f_i,	for all j

	So, for instance, try f_1 = f_3 = g_1 = g_2 = 1, otherwise, f_i & g_i
being zero.

	1 1 1 0 0 1 0
->	 0 0 1 0 1 1 1

	That the conditions are not sufficient can be seen in a variant of the
above example, with f_2 -> 1, and g_1 -> 2.

      1 1 0 0 1 0 1 1 0 1		(a)
->     0 1 0 1 1 1 0 1 1 0		(b)
->	1 1 1 0 0 1 1 0 1 0		(c)
->	 0 0 1 0 1 0 1 1 1 1
->	  0 1 1 1 1 1 0 0 0 1
->	   1 0 0 0 0 1 0 0 1 1
->	    1 0 0 0 1 1 0 1 0 0
->	     1 0 0 1 0 1 1 1 0 1	(b)

where a,b&c all satisfy the constraints on f_i & g_i, but fail to be fixpoints.

	So the only fixpoints of length < 12 are:
0
110
1110010

Andrew.

The following appears in note 1217 in brain_bogglers conference.  It seems
to be a proof that 4 numbers always melt to 1, but it avoids the use
of pascal's triangle.  Although I basically understand Pascal's triangle,
I wasn't able to understand the proof given here.

But is the following proof valid ?  It seems pretty straight forward.

Thanks.

/Eric


Re .1:  This is the core of a proof that the process will always yield four
identical numbers.

On any given step one of two things will happen.  Either the largest of the
four numbers will stay the same from one quadruplet to the next, or it will get
smaller.  Since we are dealing with positive numbers and calculating
differences, it can never get bigger.  For example:

	1 2 4 8		largest = 8
	1 2 4 7		largest = 7
	1 2 3 6		largest = 6
	1 1 3 5		largest = 5
	0 2 2 4		largest = 4
	2 0 2 4		largest = 4
	2 2 2 2		largest = 2
	0 0 0 0		largest = 0 (This always happens after all numbers are
					the same.)

So, the only way for the process to never end, is for the largest number to get
hung up some place and never drift downward.  Now, in order for the largest
number to stay the same, it must be next to a 0, as in:

	a  0  L    b
	a  L  L-b  |a-b|

For L to be the largest number for two steps, either 'a' or 'L-b' must be 0. 
In order for 'L-b' to be 0, 'b' must be equal to 'L'.  This gives us two cases:

	Case 1:				Case 2:

	0  0  L       b			a    0  L    L
	0  L  L-b     b			a    L  0    L-a
	L  b  |L-2b|  b			L-a  L  L-a  |L-2a|

For 'L' to be the largest number for three steps in case 1, 'b' must be 0.  In
case 2, 'L-a' must be 0, so 'a' must equal 'a'.  This continues the two cases:

	Case 1:				Case 2:

	0 0 L 0				L 0 L L
	0 L L 0				L L 0 0
	L 0 L 0				0 L 0 L
	L L L L				L L L L

The problem is that the next step in both cases is all 0's.  This means that no
number (except 0) can ever stay as the largest number.  Which means that the
largest number will drift downward and eventually reach 0, at which point the
process stops.

Chris

    re .7
    
    It looks OK to me, although there is one typo
    
    'L-a' must be 0, so 'a' must equal 'a'
    
    should read of course that 'L' must equal 'a'.
    
    
    Andrew's proof is more complicated because he is immediately setting
    out to solve a larger problem viz. for any number of numbers, not just
    four numbers. The technique in .7 would not be appropriate to prove
    that for 128 numbers you always end up with 128 zeroes!