login
A098065
Minimal span for an absolute difference triangle of distinct entries whose base consists of a sequence of n positive integers.
0
2, 5, 9, 14, 21, 32, 43, 58, 75, 100
OFFSET
2,1
COMMENTS
This sequence is based upon the "Triangles Programming Contest" sponsored by Al Zimmermann in 2002 and is being added here upon the request of N. J. A. Sloane. See the first link for more examples of these triangles. Note that each entry in the triangle of positive differences generated from the lower rows must be unique.
The span is defined to be the difference of the largest entry and the smallest entry in a given such triangle. The contest was to find and submit bases of lengths 2 through 25 which generated the least spans. Clearly, a(n) >= A000217(n) - 1 = A000096(n-1) for all n >= 2. The sequences given at the Final Results link are upper bounds for the current sequence.
Many of the contestants continued to improve the overall best answers after the contest ended. A Yahoo group may still exist with that discussion and posted improvements and links to relevant prior research papers on related problems with triangles. I believe that at least a(2) through a(9) were proved minimal by exhaustive searches prior to the conclusion of the contest. (I personally had proved a(2) through a(7) minimal with an interpreted PARI/GP program.).
My results in this contest for larger n were mostly based upon randomly-generated triangles to which limited heuristics were then applied to improve their spans. Much better algorithms used by the top competitors (who usually used compiled languages and sometimes multiple machines) were discussed in the Yahoo group. Perhaps some other competitor can give more known terms and the link to the discussion group/archive and tell whether it still requires membership.
EXAMPLE
For n=3, start with the base sequence 1 6 4. This generates the following triangle of positive differences with span 6 - 1 = 5, so a(3) = 5.
..3..
.5.2.
1.6.4
CROSSREFS
Cf. A000217 (triangular numbers).
Sequence in context: A276031 A011905 A306674 * A123690 A199935 A090937
KEYWORD
nonn,nice
AUTHOR
Rick L. Shepherd, Sep 12 2004
STATUS
approved