A114955 A 2/3-power Fibonacci sequence.

1, 1, 2, 3, 4, 5, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8

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

Table of n, a(n) for n=0..77.

Index entries for linear recurrences with constant coefficients, signature (1).

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

Cf. A000283, A112961, A112969, A114793.

Sequence in context: A132125 A102672 A287643 * A209384 A060207 A195932

Adjacent sequences: A114952 A114953 A114954 * A114956 A114957 A114958

Keyword

easy,nonn

Author

Jonathan Vos Post, Feb 21 2006

Status

approved