[seqfan] Re: Replacing chunks by their average (explanation)

[Lars Blomberg]

Eric,
You state that "Occams principle" should be used so that for a large "k" we should first try "2, 2k-2".
It seems to me that this is in conflict with the lexico-first requirement since "2,2,2k-4" is smaller than "2,2k-2".
/Lars

-----Ursprungligt meddelande-----
Från: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] För Eric Angelini
Skickat: den 29 mars 2015 23:11
Till: Sequence Discussion list
Ämne: [seqfan] Re: Replacing chunks by their average (explanation)


Hello Jim, Lars, Aai, Maximilian and
the others;
Here is a word of explanation.

I didn't want a trivial seq for S
but a seq S showing the "collapse"
of a chunk of same-parity integers
into a single integer.

So let's start S with a(1)=1 and a(2)=2.

S=1,2,...

If we want to illustrate a collapse
we'd better show it as quickly as
possible; so a(3)=2 (and not 1 or 3,
meaning no immediate collapse);

S=1,2,2,...

We must keep in mind that S will
collapse into itself (by definition);
this means that what we see here is
also S' -- the result of a former
collapse; thus the first "1" is replacing a chunk of integers -- but which one?

S =1,2,2,..
S'=1, 2,   2,..

The collapsing process wants a
chunk of same-parity integers
to be replaced by a single value
(integer) which is the average of
the said chunk (for example, the
chunk of even intergers 2,4,4,4,6
will be replaced by a single "4" 
 (i.e. will "collapse" into a single "4"), this "4" being the result of 2+4+4+4+6 divided by 5).

We thus write a list of "ancestors"
("chunk-ancestors") of "1" and see
what happens:

The chunk "1,1,1,1...1" will collapse
into "1";
The chunk "0,2" also;
The chunk "2,0" also;
The chunk "1,0,0,3" also;
etc.
All those are "ancestor-chunks" of "1".
But if we accept zeros we will have
problems later; as those zeros must,
at some point, be themselves the
average of another "ancestor-chunk";
and a zero-average means that the
said ancestor is made by a lot of
other zeros, etc. -- producing triviality again, which we precisely want to avoid [this is the Zero Law: no zeros can be part of S].

We bump thus into the First Law: 
- a "1"comes from another single "1",
period.

(This comes from a well-known implicit
Occam Principle: keep always the ancestor as simple as possible in order not to get stuck.)

Let's list now the ancestors of "2";
they are of the type "1,3" and "3,1"
and of the type "2,2,2,2,2,2...2". 
[We cannot mix even and odd terms
in the "ancestor-chunk" -- as the said
chunk would be parity-inhomogeneous
(like "1,2,3"), which is forbidden].
The "1,3" and "3,1" types could also
look like "1,3,3,1" or "3,1,3,1,3,1" of
course.

We are almost equipped now to
build simultaneously S and S' -- the
only missing thing being the Second
Law:
- Two "1"´s _must_ always be separated
by an odd quantity of integers.
[It took me almost an hour to find and
understand this (now) obvious 2d Law...]

As we want S to be the lexico-first
"collapsing to itself" seq, we will
always try to produce ancestors-chunks
of "k" of the type "1, 2k-1", else
"2, 2k-2" (this is due again to the
Occam Principle: simple things first).

Let's try this start for S:

S =1,2,2,1,3,...
S'=1  2    2

This looks promising but... the First Law has not being respected and problems arise immediately; if S starts like 1,2,2,1,3,...
this means that S' will look the same
and will "dictate" the "ancestors" of S
(the S' line is the line with the averages):

S =1,2,2,1,3,...
S'=1  2    2    1    3

The second "1" of S' dictates a "1" in S:

S =1,2,2,1,3, 1,...
S'=1  2    2    1    3

But we see here that this "1" is of the
same parity as the chunk "1,3" -- thus
ruining the process, forcing us to
write S and S' like this:

S =1,2,2,1,3, 1,...
S'=1  2      3

... they are not the same anymore --
contradiction.

This comes from the break of the First Law: there were only two integers between the two "1"'s of S.
Can we fix that like this (inverting
"1,3" into "3,1"):

S =1,2,2,3,1,...
S'=1  2    2    3   1

Well, no; another contradiction will
appear because of the last "1" of S'
which will dictate this behaviour of
S:

S =1,2,2,3,1, ... ,1
S'=1  2    2    3   1

We see here that the "3" of S' cannot
produce an "ancestory" in S that will
fit _between_ the "1"'s of S; this is
because of the Third Law:

- An odd "average" cannot produce a
chunk of even integers that are in odd quantity in the said chunk.
That is, "3" cannot be the average
of a chunk like [a,b,c,...n] where all
terms are even AND where those
terms a,b,c,...n are in a odd quantity
(those two requirements are dictated
by the First and the Second Law,
the First saying that à "1" in S' gives
a "1" in S and the Second saying
that between two "1"'s of S there
_must_ be an odd quantity of terms.

We thus try this start for S (and S'):

S =1,2,2,2,1,3,...
S'=1   2    2    2    1    3

This will work and produce the S I've
submitted two days ago.

Hope this is clear now -- and fun!
Best,
É.
---- ---- ---- ---- ---- ---- 
> S=
1,2,2,2,1,3,2,2,1,2,4,3,1,2,1,2,1,7,2,4,1,2,1,2,1,2,12,3,1,4,1,2,1,2,1,2,1,23,
2,4,1,4,1,2,1,2,1,2,1,2,44,3,14,14,1,2,1,2,1,2,1,2,1,87,2,4,1,4,1,4,1,2,1,2,1,
2,1,2,1,2,172,3,1,4,1,4,1,4,1,2,1,2,1,2,1,2,1,2,1,343,...

> Hello SeqFans,
Replace in S all chunks of same-parity integers by the average of the said chunk and you will get S back.

Example:
- the first chunk is made by 1, -- replace it with 1;
- the second chunk is 2,2,2, -- replace it with 2; -the third chunk is 1,3, -- replace it with 2; -the fourth chunk is 2,2, -- replace it with 2; -the fifth chunk is made by 1, -- replace it with 1; -the sixth chunk is made by 2,4, -- replace it by 3; etc.
The replacements so far have been
1,2,2,2,3,1... which rebuilds S.

One quickly finds this array where the rightmost diagonal is A023105.

---
1,
2,
2,
2,1,3,
2,2,1,2,4,
3,1,2,1,2,1,7,
2,4,1,2,1,2,1,2,12,
3,1,4,1,2,1,2,1,2,1,23,
2,4,1,4,1,2,1,2,1,2,1,2,44,
3,1,4,1,4,1,2,1,2,1,2,1,2,1,87,
2,4,1,4,1,4,1,2,1,2,1,2,1,2,1,2,172,
3,1,4,1,4,1,4,1,2,1,2,1,2,1,2,1,2,1,343,
...

Best,
É.
Catapulté de mon aPhone

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/