login
A008062
a(n) = maximal value of m such that an n X m radar array exists. (A (0,1) matrix A such that any horizontal shift of A overlaps A in at most a single 1.)
2
2, 4, 7, 10, 12, 15, 18, 21, 24, 26, 29, 32, 35, 37, 40, 43
OFFSET
1,1
COMMENTS
Also, maximal length of a 2-surprising sequence in n symbols. (A sequence of symbols is 2-surprising if, for every pair of symbols X and Y, not necessarily distinct and every distance D, there is at most one position in t he sequence where X precedes Y by distance D.) - John W. Layman, Nov 17 2003
Dan Hoey (Jan 13 2006) points out that the equivalence of the two definitions is a consequence of the equivalence (for any sequence s_1,s_2,...) of "Exists i,j,k,l : s_i = s_j, s_k = s_l and i-k = j-l" and "Exists i,j,k,l : s_i = s_j, s_k = s_l and i-j = k-l".
REFERENCES
J. Hamkins and K. Zeger, Improved bounds on maximum size binary radar arrays, IEEE Trans. Inform. Theory, 43 (1997), 997-1000.
Dennis E. Shasha, Puzzling Adventures, Scientific American 289 (#12, 2003), 22.
EXAMPLE
{0,1,1,2,0,3,2,3,1,0}, {0,0,1,2,3,2,4,1,0,4,3,1} and {0,0,1,2,3,1,4,5,2,5,0,3,4,1,0} are 2-surprising sequences of 4, 5 and 6 symbols, respectively and no longer sequences of 4,5, or 6 symbols exist, so a(4)=10, a(5)=12 and a(6)=15.
a(7) = 18: example: AABCDBEFGCGEADFBAC and there are no longer strings. - Jeffrey Shallit, Dec 03 2003
a(8) = 21: example: ABACDEFGDHECHGBBFEADC and there are no longer strings.
a(9) = 24: example: ABCDDEFEGHIFCIBAHGBECAFD and there are no longer strings.
a(10) = 26: example: AABCBDEFGHEIJCDJGAIDFHBACE and there are no longer strings.
a(11) = 29; example: AABCDECFGHIHJDKBEIJKGFACEBAHD and there are no longer strings.
a(12) = 32; example: AABCDEFGHGIJKELFCLKBDJIHBAFDGACE and there are no longer strings. - Dan M. Shaw (dan(AT)aloha.com), Dec 14 2003 and Jan 11 2004
CROSSREFS
Cf. A089973.
Sequence in context: A047539 A190521 A186224 * A089972 A276209 A062429
KEYWORD
nonn
EXTENSIONS
Next term is 46 or 47.
STATUS
approved