OFFSET
0,3
COMMENTS
a(n) is also the minimum number of distinct palindromes (not counting the empty string) occurring as substrings of an n-bit binary string. For example, the string 11001 contains the five distinct palindromes 0, 00, 1, 11, and 1001. In fact, every 5-bit binary string contains five distinct palindromes, so a(5) = 5. - Austin Shapiro, Feb 15 2023
LINKS
FORMULA
a(0) = a(1) = 1, for n>1 a(n) = ceiling(a(n-1)^(2/3) + a(n-2)^(2/3)).
a(n) = 8 for all n>8.
Euler transform of length 8 sequence [ 1, 1, 1, 0, 0, -1, 0, -1]. - Michael Somos, Aug 31 2006
G.f.: (1-x^6)(1-x^8)/((1-x)(1-x^2)(1-x^3)). - Michael Somos, Aug 31 2006
EXAMPLE
a(2) = ceiling(a(0)^(2/3) + a(1)^(2/3)) = ceiling(1^(2/3) + 1^(2/3)) = 2.
a(3) = ceiling(a(1)^(2/3) + a(2)^(2/3)) = ceiling(1^(2/3) + 2^(2/3)) = ceiling(2.58740105) = 3.
a(4) = ceiling(2^(2/3) + 3^(2/3)) = ceiling(3.66748488) = 4.
a(5) = ceiling(3^(2/3) + 4^(2/3)) = ceiling(4.59992592) = 5.
a(6) = ceiling(4^(2/3) + 5^(2/3)) = ceiling(5.44385984) = 6.
a(7) = ceiling(5^(2/3) + 6^(2/3)) = ceiling(6.22594499) = 7.
a(8) = ceiling(6^(2/3) + 7^(2/3)) = ceiling(6.96123296) = 7.
MATHEMATICA
nxt[{a_, b_}]:={b, Ceiling[b^(2/3)+a^(2/3)]}; Transpose[NestList[nxt, {1, 1}, 80]][[1]] (* Harvey P. Dale, Jan 03 2013 *)
PROG
(PARI) {a(n)=if(n<1, n==0, if(n>8, 8, n-(n>7)))} /* Michael Somos, Aug 31 2006 */
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Jonathan Vos Post, Feb 21 2006
STATUS
approved