[seqfan] Re: Noninterfering picket fence seeds

[franktaw at netscape.net]

See marked point below; this should be 4n+6, not 6n+4. In fact, 20 is 
next at this point.

I think the lexicographically first sequence starts:

1,3,6,10,20,32,112

All remaining terms are == 4 (mod 12).

Franklin T. Adams-Watters

-----Original Message-----
From: William Keith <wjk26 at drexel.edu>

On Jun 10, 2010, at 5:34 PM, franktaw at netscape.net wrote:

> Another question occurs to me.
>
> Are there infinite sets with this property? I think there must be, 
but
> it is curiously hard to construct one. If there is,what is the
> lexicographically first such set?
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Ron Hardin <rhhardin at att.net>
>
> ...
>
> %N A000001 Smallest range 1..a(n) that permits n integers x() in
> 1..a(n) to
> exist with (x(i)-x(j)) mod (x(k)-x(j)) nonzero whenever i,j,k are
> disjoint.
> %C A000001 Maximal non-interfering picket-fence seeds: a picket fence
> extended
> from any pair in the set encounters no other member of the set

You are looking for an infinite set with the property that (x(i)-x(j)) 
mod
(x(k)-x(j)) nonzero for all distinct i,j,k?

Sounds like a job for a sieve.  However, we never want to fill up all 
possible
residue classes, so I'll never take the first available choice, but the 
next.
This may not be lexicographically first, but it should work.

Start with x(1) = 1.  The next available choice is 2, but as you can 
see making
the first choice here *immediately* ends the list.  Strike 2 as an
impossibility.

Next is 3.  Set x(2) = 3.  Extending from 1 (i.e., with j=1), no other 
entry can
have x(i) - x(1) a multiple of 2, so all further entries are even; 
strike 2n+1.
The next choice is 4, but that's no good again; skip it.

Next value is 6.  Set x(3) = 6.  Extending from 1, no other entry can 
have x(i)
- x(1) a multiple of 5, so strike all 5n+1, and from 3, differences 
cannot be 3,
so strike all 3n.  Next value is 8, but again this terminates our list. 
 Skip.

Next value is 10.  Set x(4) = 10.  Extending from 1, no other entry can 
have
x(i) - x(1) a multiple of 9; strike 9n+1.  From 3, 7n+3; from 6, 6n+4.  
Strike
==============================================^
these.  Next entry is 14, and for once this doesn't immediately 
terminate the
list, but skip it.

Next is 20.  x(5) = 20.  Strike 19n+1, 17n+3, 14n+6, 10n+10.  Next is 
32, but
skip, and pick 44.

At a first glance, I think giving ourselves "space" like this 
guarantees that
we'll always have more choices available for the next stage, and the 
sieve
guarantees the lack of arithmetic progressions we're seeking.  If so, 
rigorous
proof should probably not be too hard.

William

_______________________________________________

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