| Displaying 1-4 of 4 results found.
page
1
Sizes of Garden of Eden partitions in Bulgarian Solitaire, given in the same order as the runlength codes of the corresponding partitions ( A227753).
+20
3
3, 4, 6, 8, 5, 7, 5, 7, 9, 6, 10, 8, 6, 9, 11, 8, 12, 10, 13, 10, 14, 12, 7, 11, 15, 12, 9, 13, 11, 8, 10, 7, 11, 9, 7, 10, 12, 14, 9, 13, 11, 14, 16, 11, 15, 18, 13, 8, 14, 17, 12, 16, 13, 15, 10, 14, 12, 9, 11, 13, 8, 12, 10, 8, 12, 14, 16, 11, 15, 13, 16, 18
COMMENTS
Each n occurs A123975(n) times in total.
a(n) = Bulgarian solitaire operation applied to the partition encoded in the runlengths of binary expansion of n.
+10
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
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).
Number of Garden of Eden partitions of n in Bulgarian Solitaire.
+10
6
0, 0, 1, 1, 2, 3, 5, 7, 10, 14, 20, 27, 37, 49, 66, 86, 113, 147, 190, 243, 311, 394, 499, 627, 786, 980, 1220, 1510, 1865, 2294, 2816, 3443, 4202, 5110, 6203, 7507, 9067, 10923, 13135, 15755, 18865, 22540, 26885, 32001, 38032, 45112, 53430, 63171
FORMULA
a(n) = Sum_{j>=1} (-1)^(j+1)*p(n-b(j)) where b(j) = 3*j*(j+1)/2 ( A045943) and p(n) is the number of partitions of n (see A000041). See Hopkins & Sellers. - Michel Marcus, Sep 26 2018 a(n) ~ exp(Pi*sqrt(2*n/3)) / (8*n*sqrt(3)) * (1 - (1/(2*Pi) + 19*Pi/144) / sqrt(n/6)). - Vaclav Kotesovec, May 26 2023
MAPLE
p:=product(1/(1-q^i), i=1..200)*sum((-1)^(r-1)*q^((3*r^2+3*r)/2), r=1..200):s:=series(p, q, 200): for j from 0 to 199 do printf(`%d, `, coeff(s, q, j)) od: # James A. Sellers, Nov 30 2006
PROG
(PARI) my(N=50, x='x+O('x^N)); concat([0, 0], Vec(1/prod(k=1, N, 1-x^k)*sum(k=1, N, (-1)^(k-1)*x^(3*k*(k+1)/2)))) \\ Seiichi Manyama, May 21 2023
a(n) is the number of occurrences of n in A226062.
+10
3
1, 1, 1, 1, 1, 0, 2, 1, 1, 1, 0, 1, 2, 1, 2, 1, 1, 1, 0, 2, 0, 0, 0, 1, 2, 2, 0, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 0, 1, 2, 1, 0, 0, 0, 1, 0, 1, 1, 2, 2, 1, 3, 1, 0, 1, 2, 2, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 2, 1, 0, 1, 2, 2, 0, 0, 0, 2, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0
FORMULA
In the following formula [] stands for Iverson brackets. Essentially we are just naively counting the integers which A226062 maps to n. A000225 is the guaranteed upper limit for the runlength codes for the partitions of size n:
PROG
(Scheme, a naive implementation which always begins search from zero)
;; The following function implements sum_{i=lowlim..uplim} intfun(i)
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))
CROSSREFS
A227753 gives the positions of zeros.
Search completed in 0.007 seconds
| 