Two ordering problems

[franktaw at netscape.net]

True; for an infinite sequence, a must be rational.  (At which point
all that matters about c is the value of floor(c * denominator(a)), so
c can but does not have to be rational.)

However, the question posed really only looks at finite initial
sequences, so it is not necessary to restrict a in this way.  The same
sequence of length n will always be generated by a range of values
of a and c.

It should be clear that every rational a > 1 can be obtained: if
a = u/v, we take sequence X to be r*(u-v)*n + k_1 and Y to be
r*v*n + k_2, where k_1 and k_2 are not congruent modulo r;
by taking r big enough and suitable values of k_1 and k_2, we
can get the value of c that we want.  (There are constraints on
the value of c; certainly at least -c < a.  I haven't worked out
exactly what all the constraints are.)

(Depending on the exact definition of the problem, which I don't
remember right now, there may be a problem with initial values.
That is, if X is 4n, and Y is 6n+999, we will start with a lot of X's
before the X,X,Y,X,Y pattern appears.  If the formulation is that
X and Y must each be all positive (or non-negative) numbers
with a specified congruence, we don't have this problem.)

Franklin T. Adams-Watters

-----Original Message-----
From: Max Alekseyev <maxale at gmail.com>

At first glance, this property is also only necessary but not
sufficient (unless proved otherwise), since in David's sequence the
coefficients a and c are related to each other. Hence, a sequence
generated by floor(a*n+c) for some (arbitrary) a and c may not
necessary be possible to generate in a way proposed by David.

Regards,
Max

On Wed, Aug 27, 2008 at 3:59 PM,  <franktaw at netscape.net> wrote:
> The property you need is similar to that for a Beatty sequence.  The
> position
> of the nth X (or Y) in the sequence will be floor(a*n+c) for some a 
and c.
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: David Wilson <dwilson at gambitcomm.com>
>
> Max Alekseyev wrote:
>>
>> It appears that the sequence is good iff the number of Y (resp. X)
>> symbols between any two neighboring X (resp. Y) symbols either equals
>> an integer constant or varies between some two consecutive integer
>> values.
>> In the aforementioned sample sequence
>> X,Y,X,Y,X,X,Y,X,Y,X,X,Y,...
>> the distance between every two neighboring X's is 0 or 1 and the
>> distance between every two neighboring Y's is 1 or 2.
>>
>> With this characterization in mind, it is easy to compute the number
>> of good sequences of length n.
>>
> Your observation is certainly a property of good sequences, indeed the
> distance between any two adjacent X's will always be k or k+1 for 
some k
> (similarly for adjacent Y's). This is necessary for a good sequence, 
but
> not sufficient. For example
>
> X,Y,X,Y,X,Y,X,X,Y,X,X
>
> is not good.
>