|
| |
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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 (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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
