login
A207831
Square array such that T[n+1,k] = | T[n,k] +- T[n,k+1] |, filling antidiagonals with the smallest possible positive integers not occurring earlier.
2
1, 2, 3, 4, 6, 9, 7, 11, 5, 14, 8, 15, 26, 21, 35, 10, 18, 33, 59, 38, 73, 13, 23, 41, 74, 133, 95, 22, 12, 25, 48, 89, 163, 30, 65, 43, 16, 28, 53, 101, 190, 27, 57, 122, 79, 20, 36, 64, 117, 218, 408, 381, 324, 202, 123, 19, 39, 75, 139, 256, 474, 66, 315, 639, 437, 314, 32, 51, 90, 165, 304, 560, 86, 152, 467, 172, 265, 49
OFFSET
1,2
COMMENTS
The first 50 antidiagonals of this table were computed by A. Groeneveld.
The table A207826 is a variant obtained by discarding a candidate for T[1,k] as soon as the "greedy way" of filling the antidiagonal (choose absolute difference or sum if the former is already used, but don't trace back to reconsider earlier choices) does not work.
The present version is computed by considering all possibilities in order to have the smallest possible T[1,k], cf. the example.
LINKS
E. Angelini, Tableau avec soustractions/additions, Feb 19 2012
E. Angelini, Tableau avec soustractions/additions [Cached copy, with permission]
EXAMPLE
From M. F. Hasler, Feb 23 2012: (Start)
The triangle (upper left of the square array) starts
row 1: 1 2
row 2: 3 (because |1-2|=1 already occurred).
The next antidiagonal reads (4, 4+2=6, 6+3=9) (since 4-2=2 and 6-3=3 are already used earlier), and so on.
The 25th antidiagonal can start with (83, 130, 223, 443, 393, 174, 569, 302, 890, 279, 181, 155, 398, 255, 102, 1029, 1679, 1256, 840, 116, ...). Then one could put 597-116=481. However, at the next step, both 481+88 and 481-88 occurred earlier (here in the very same antidiagonal). Therefore, we revise the earlier choice and change it to 597+116=713. Then the subsequent values in this antidiagonal are (..., 713+88=801, 801-505=296, 296-126=170, 911-170=741). The table A207826 is obtained if we do not reconsider the earlier choice of "-" vs. "+", but discard the whole antidiagonal once the greedy method cannot be continued down to the bottom, and start over with the next possible element in the first row. This would yield (91, 138, 231, 451, 401, 968, 573, ..., 549) for the 25th antidiagonal.
(End)
PROG
(PARI) [Contribution by M. F. Hasler, Feb 20 2012] (Start)
/* assumes that the first line A207829 is already computed. NOTE: This code does not yield the correct values T[n, k] beyond n+k=25 */
{T=matrix(#A=A207829, #A); u=Set(T[1, ]=A); for(j=2, #T, for(i=2, j, setsearch(u, T[i, j]=abs(T[i-1, j-1]-T[i-1, j]))&T[i, j]=T[i-1, j-1]+T[i-1, j]; u=setunion(u, Set(T[i, j]))))}
for(j=1, 12, for(i=1, j, print1(T[i, j]", "))) \\ (End)
CROSSREFS
Sequence in context: A098168 A306441 A370981 * A207826 A035312 A056230
KEYWORD
nonn,tabl
AUTHOR
Eric Angelini, Feb 20 2012
STATUS
approved