A053599 Number of nonempty subsequences {s(k)} of 1..n such that the difference sequence is palindromic.

1, 3, 7, 13, 23, 37, 59, 89, 135, 197, 291, 417, 607, 861, 1243, 1753, 2519, 3541, 5075, 7121, 10191, 14285, 20427, 28617, 40903, 57285, 81859, 114625, 163775, 229309, 327611, 458681, 655287, 917429, 1310643, 1834929, 2621359, 3669933, 5242795, 7339945

Offset: 1

Author

John W. Layman, Jan 19 2000

Keywords

• nonn
• easy

Comments

Equals (n-1)-th row sums of triangle A152202. - Gary W. Adamson, Nov 29 2008

a(n) is the number of positive integers < 2^n such that the binary representation of the odd part is palindromic; i.e., palindromic without the final 0's. - Andrew Woods, May 19 2012

a(n) is the number of ideals of the quotient ring Z_{2^n}[u]/ for indeterminate u. - Fatih Temiz, Oct 11 2017

Conjecture: let b(n) be the number of subsets S of {1,2,...,n} having more than one element such that (sum of least two elements of S) > max(S). Then b(0) = b(1) = 0 and b(n+2) = a(n+1) for n >= 0. - Clark Kimberling Sep 27 2022

Examples

			For n=4 the 13 sequences are 1,2,3,4,12,13,14,23,24,34,123,234,1234.
		

Links

• Andrew Woods, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (2,1,-4,2).

Crossrefs

Cf. A027383 (first differences), A016116 (second differences).

Cf. A152202.

Programs

Mathematica

t={1,1};Do[AppendTo[t,t[[-2]]+t[[-1]]];AppendTo[t,2*t[[-2]]],{n,40}];Nest[Accumulate,t,2] (* Vladimir Joseph Stephan Orlovsky, Jan 29 2012 *)

Formula

a(1)=1, a(2)=3 and, for n > 2, a(n) = 2*a(n-2) + 2*n - 1.

G.f.: x*(1+x)/((1-x)^2*(1-2*x^2)). - Colin Barker, Mar 28 2012

a(n) = 5*2^((n+1)/2) - 2*n - 7 for odd n, 7*2^(n/2) - 2*n - 7 for even n. - Andrew Woods, May 19 2012

Extensions

Corrected by T. D. Noe, Nov 08 2006