[seqfan] Re: Noninterfering picket fence seeds
franktaw at netscape.net
franktaw at netscape.net
Fri Jun 11 01:05:06 CEST 2010
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/
More information about the SeqFan
mailing list