A117855 Number of nonzero palindromes of length n (in base 3).

2, 2, 6, 6, 18, 18, 54, 54, 162, 162, 486, 486, 1458, 1458, 4374, 4374, 13122, 13122, 39366, 39366, 118098, 118098, 354294, 354294, 1062882, 1062882, 3188646, 3188646, 9565938, 9565938, 28697814, 28697814, 86093442, 86093442, 258280326, 258280326, 774840978

Offset: 1

Author

Martin Renner, May 02 2006

Keywords

• nonn
• base
• easy

Comments

See A225367 for the sequence that counts all base 3 palindromes, including 0 (and thus also the number of n-digit terms in A006072). -- A nonzero palindrome of length L=2k-1 or of length L=2k is determined by the first k digits, which then determine the last k digits by symmetry. Since the first digit cannot be 0, there are 2*3^(k-1) possibilities. - M. F. Hasler, May 05 2013

From Gus Wiseman, Oct 18 2023: (Start)

Also the number of subsets of {1..n} with n not the sum of two subset elements (possibly the same). For example, the a(0) = 1 through a(4) = 6 subsets are:

{} {} {} {} {}

{1} {2} {1} {1}

{2} {3}

{3} {4}

{1,3} {1,4}

{2,3} {3,4}

For subsets with no subset summing to n we have A365377.

Requiring pairs to be distinct gives A068911, complement A365544.

The complement is counted by A366131.

(End) [Edited by Peter Munn, Nov 22 2023]

Examples

			The a(3)=6 palindromes of length 3 are: 101, 111, 121, 202, 212, and 222. - _M. F. Hasler_, May 05 2013
		

Links

• Index entries for linear recurrences with constant coefficients, signature (0,3).

Crossrefs

Cf. A050683 and A070252.

Bisections are both A025192.

A093971/A088809/A364534 count certain types of sum-full subsets.

A108411 lists powers of 3 repeated, complement A167936.

Cf. A004526, A004737, A008967, A038754, A046663, A167762, A365376, A366130.

Programs

Mathematica

With[{c=NestList[3#&,2,20]},Riffle[c,c]] (* Harvey P. Dale, Mar 25 2018 *)
Table[Length[Select[Subsets[Range[n]],!MemberQ[Total/@Tuples[#,2],n]&]],{n,0,10}] (* Gus Wiseman, Oct 18 2023 *)

PARI

A117855(n)=2*3^((n-1)\2) \\ - M. F. Hasler, May 05 2013

Python

def A117855(n): return 3**(n-1>>1)<<1 # Chai Wah Wu, Oct 28 2024

Formula

a(n) = 2*3^floor((n-1)/2).

a(n) = 2*A108411(n-1).

From Colin Barker, Feb 15 2013: (Start)

a(n) = 3*a(n-2).

G.f.: -2*x*(x+1)/(3*x^2-1). (End)

Extensions

More terms from Colin Barker, Feb 15 2013