|
| |
|
|
A226062
|
|
a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.
|
|
16
|
|
|
|
0, 1, 3, 2, 13, 7, 6, 6, 11, 29, 15, 58, 9, 14, 4, 14, 19, 27, 61, 54, 245, 31, 122, 52, 27, 25, 30, 50, 25, 12, 12, 30, 35, 23, 59, 46, 237, 125, 118, 44, 235, 501, 63, 1002, 233, 250, 116, 40, 51, 19, 57, 38, 229, 62, 114, 36, 59, 17, 28, 34, 57, 8, 28, 62
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
For this sequence the partitions are encoded in the binary expansion of n in the same way as in A129594.
In "Bulgarian solitaire" a deck of cards or another finite set of objects is divided into one or more piles, and the "Bulgarian operation" is performed by taking one card from each pile, and making a new pile of them. The question originally posed was: on what condition the resulting partitions will eventually reach a fixed point, that is, a collection of piles that will be unchanged by the operation. See Martin Gardner reference and the Wikipedia-page.
A037481 gives the fixed points of this sequence, which are numbers that encode triangular partitions: 1 + 2 + 3 + ... + n.
A227752(n) tells how many times n occurs in this sequence, and A227753 gives the terms that do not occur here.
Of further interest: among each A000041(n) numbers j_i: j1, j2, ..., jk for which A227183(j_i)=n, how many cycles occur and what is the size of the largest one? (Both are 1 when n is in A000217, as then the fixed points are the only cycles.) Cf. A185700, A188160.
Also, A123975 answers how many Garden of Eden partitions there are for the deck of size n in Bulgarian Solitaire, corresponding to values that do not occur as the terms of this sequence.
|
|
|
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
|
Other identities:
A227183(a(n)) = A227183(n). [This operation doesn't change the total sum of the partition.]
|
|
|
EXAMPLE
|
5 has binary expansion "101", whose runlengths are [1,1,1], which are converted to nonordered partition {1+1+1}.
6 has binary expansion "110", whose runlengths are [1,2] (we scan the runs of bits from right to left), which are converted to nonordered partition {1+2}.
7 has binary expansion "111", whose list of runlengths is [3], which is converted to partition {3}.
In "Bulgarian Operation" we subtract one from each part (with 1-parts vanishing), and then add a new part of the same size as there originally were parts, so that the total sum stays same.
Thus starting from a partition encoded by 5, {1,1,1} the operation works as 1-1, 1-1, 1-1 (all three 1's vanish) but appends part 3 as there originally were three parts, thus we get a new partition {3}. Thus a(5)=7.
From the partition {3} -> 3-1 and 1, which gives a new partition {1,2}, so a(7)=6.
For partition {1+2} -> 1-1 and 2-1, thus the first part vanishes, and the second is now 1, to which we add the new part 2, as there were two parts originally, thus {1+2} stays as {1+2}, and we have reached a fixed point, a(6)=6.
|
|
|
PROG
|
(MIT/GNU Scheme)
(define (A226062 n) (if (zero? n) n (ascpart_to_binexp (bulgarian-operation (binexp_to_ascpart n)))))
(define (bulgarian-operation ascpart) (let loop ((newpart (list (length ascpart))) (ascpart ascpart)) (cond ((null? ascpart) (sort newpart <)) (else (loop (if (= 1 (car ascpart)) newpart (cons (- (car ascpart) 1) newpart)) (cdr ascpart))))))
;; The rest is the same code as used in A129594:
(define (binexp_to_ascpart n) (let ((runlist (reverse! (binexp->runcount1list n)))) (PARTSUMS (cons (car runlist) (map -1+ (cdr runlist))))))
(define (ascpart_to_binexp ascpart) (runcount1list->binexp (reverse! (cons (car ascpart) (map 1+ (DIFF ascpart))))))
(define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))
(define (runcount1list->binexp lista) (let loop ((lista lista) (s 0) (state 1)) (cond ((null? lista) s) (else (loop (cdr lista) (+ (* s (expt 2 (car lista))) (* state (- (expt 2 (car lista)) 1))) (- 1 state))))))
(define (DIFF a) (map - (cdr a) (reverse! (cdr (reverse a)))))
(define (PARTSUMS a) (cdr (reverse! (fold-left (lambda (psums n) (cons (+ n (car psums)) psums)) (list 0) a))))
|
|
|
CROSSREFS
|
Cf. A037481 (gives the fixed points).
Cf. A227752 (how many times n occurs here).
Cf. A227753 (numbers that do not occur here).
Cf. A129594 (conjugates the partitions encoded with the same system).
|
|
|
KEYWORD
|
nonn,base
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
