login
A227141
Array A(n,k) where A(1,k)=1 for row 1, and subsequent rows A(n > 1, k) are computed by recurrences related to Bulgarian Solitaire; square array A(n,k), with row n >= 1, column k >= 0, read by antidiagonals.
2
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 4, 3, 2, 1, 1, 1, 1, 3, 3, 3, 2, 1, 1, 1, 2, 2, 5, 4, 3, 2, 1, 1, 1, 1, 3, 4, 4, 4, 3, 2, 1, 1, 1, 2, 4, 4, 6, 5, 4, 3, 2, 1, 1, 1, 1, 2, 3, 5, 5, 5, 4, 3, 2, 1, 1, 1, 2, 3, 4, 5, 7, 6, 5, 4, 3, 2, 1, 1
OFFSET
0,12
COMMENTS
The initial terms give the summands of the partitions (or: number of parts, when shifted once) that occur in the main trunk of Bulgarian solitaire tree computed for a pack containing 1+2+...+n cards.
The irregular table A227147 gives just the palindromic subsequence from each row. After that part, the recurrence on row n always leads to a sequence of period n.
REFERENCES
Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.
LINKS
Ethan Akin and Morton Davis, "Bulgarian solitaire", American Mathematical Monthly 92 (4): 237-250. (1985).
FORMULA
The recurrence for the r-th row of the table (after the first row, which contains a constant sequence A000012) is defined as follows:
a_r(0) = 1; a_r(0<n<r) = n, a_r(n=r) = r-1, a_r(n=(r+1)) = n, a_r(n<2r) = r, and otherwise (for values n>=2r), a_r(n) = the least natural number k such that a_r(n-k-1) < k+1.
See also the given Scheme program.
EXAMPLE
The top left corner of the array begins
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...
1, 1, 2, 2, 4, 3, 2, 3, 4, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, ...
1, 1, 2, 3, 3, 5, 4, 4, 3, 4, 5, 4, 3, 4, 4, 5, 3, 4, 4, 4, 3, 4, ...
1, 1, 2, 3, 4, 4, 6, 5, 5, 5, 4, 5, 6, 5, 5, 4, 5, 5, 6, 5, 4, 5, ...
...
For row 3, the recurrence manifests itself as:
a_3(0) = 1; a_3(0<n<3) = n (i.e., a_3(1)=1, a_3(2)=2), a_3(3) = 2, a_3(4) = 4, a_3(4<n<6) (that is, a_3(5)) = 3, and after that, for values n>=6, a_3(n) = the least natural number k such that a_3(n-k-1) < k+1.
As a_3(6-0-1) = a_3(5) = 3 is not less than 1, nor a_3(6-1-1) = a_3(4) = 2 is not less than 2, but a_3(6-2-1) = a_3(3) = 2 IS less than 3 (2+1), the sought value of k is 2, and a_3(6)=2.
PROG
(Scheme, with Antti Karttunen's IntSeq-library, using memoizing macros definec and implement-cached-function):
(define (A227141 n) (A227141bi (+ 1 (A002262 n)) (A025581 n)))
(define (A227141bi row col) ((rowfun-for-A227141 row) col))
(definec (rowfun-for-A227141 n) (if (< n 2) (lambda (k) n) (implement-cached-function 0 (rowfun-n k) (cond ((zero? k) 1) ((< k n) k) ((= k n) (- n 1)) ((= k (+ n 1)) k) ((< k (* 2 n)) n) (else (let loop ((i 1)) (if (< (rowfun-n (- k i)) i) (- i 1) (loop (+ i 1)))))))))
CROSSREFS
Cf. A227147.
Sequence in context: A337199 A344879 A090189 * A284997 A369367 A306709
KEYWORD
nonn,tabl
AUTHOR
Antti Karttunen, Jul 03 2013
STATUS
approved