A037481 Base 4 digits are, in order, the first n terms of the periodic sequence with initial period 1,2.

0, 1, 6, 25, 102, 409, 1638, 6553, 26214, 104857, 419430, 1677721, 6710886, 26843545, 107374182, 429496729, 1717986918, 6871947673, 27487790694, 109951162777, 439804651110, 1759218604441, 7036874417766, 28147497671065

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• base
• easy

Comments

The terms have a particular pattern in their binary expansion, which encodes for a "triangular partition" when runlength encoding of unordered partitions are used (please see A129594 for how that encoding works).

n a(n) same in binary run lengths unordered partition

0 0 0 [] {}

1 1 1 [1] {1}

2 6 110 [2,1] {1+2}

3 25 11001 [2,2,1] {1+2+3}

4 102 1100110 [2,2,2,1] {1+2+3+4}

5 409 110011001 [2,2,2,2,1] {1+2+3+4+5}

6 1638 11001100110 [2,2,2,2,2,1] {1+2+3+4+5+6}

7 6553 1100110011001 [2,2,2,2,2,2,1] {1+2+3+4+5+6+7}

8 26214 110011001100110 [2,2,2,2,2,2,2,1] {1+2+3+4+5+6+7+8}

9 104857 11001100110011001 [2,2,2,2,2,2,2,2,1] {1+2+3+4+5+6+7+8+9}

These partitions are the only fixed points of "Bulgarian Solitaire" operation (see Gardner reference or Wikipedia page), and thus the terms of this sequence give the fixed points for A226062 which implements that operation (using the same encoding for partitions). This also implies that these partitions are the roots of the game trees constructed for decks consisting of 1+2+3+...+k cards. See A227451 for the encoding of the corresponding tops of the main trunks of the same trees. - Antti Karttunen, Jul 12 2013

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

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Wikipedia, Bulgarian solitaire
• Index entries for linear recurrences with constant coefficients, signature (4,1,-4).

Crossrefs

Cf. A014985, A015521, A227451.

Cf. A037487 (decimal digits 1,2).

The right edge of the table A227452. The fixed points of A226062.

Programs

Magma

I:=[0, 1, 6]; [n le 3 select I[n] else 4*Self(n-1)+Self(n-2)-4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 21 2012

Mathematica

LinearRecurrence[{4,1,-4},{0,1,6},40] (* Vincenzo Librandi, Jun 21 2012 *)
Module[{nn=30,ps},ps=PadRight[{},nn,{1,2}];Table[FromDigits[Take[ps,n],4],{n,0,nn}]] (* Harvey P. Dale, Jul 18 2013 *)

PARI

concat(0, Vec(x*(2*x+1)/((x-1)*(x+1)*(4*x-1)) + O(x^100))) \\ Colin Barker, Apr 30 2014

PARI

a(n) = 2<<(2*n) \ 5; \\ Kevin Ryde, Jun 24 2023

Python

def A037481(n): return (1<<(n<<1|1))//5 # Chai Wah Wu, Jun 28 2023

Scheme

(define (A037481 n) (/ (- (/ (+ (expt 4 (1+ n)) (expt -1 n)) 5) 1) 2)) ;; Using Ralf Stephan's direct formula - Antti Karttunen, Jul 12 2013

Formula

a(n) = ((4^(n+1) - (-1)^(n+1))/5 - 1)/2. - Ralf Stephan

a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3). - Vincenzo Librandi, Jun 21 2012

a(n) = A226062(A129594(A227451(n))). [See page 465 in Gardner's book] - Antti Karttunen, Jul 12 2013

G.f.: x*(2*x+1) / ((x-1)*(x+1)*(4*x-1)). - Colin Barker, Apr 30 2014