[seqfan] Re: Noninterfering picket fence seeds

[William Keith]

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