cp's OEIS Frontend

a(0) = 1; a(2t)=a(t), a(4t+1)=8*a(t), a(4t+3)=2*a(2t+1)+8*a(t) for t >= 0. (Conjectured by Hrothgar, Jul 11 2014; proved by N. J. A. Sloane, Oct 04 2014.)

For n >= 2, a(n) = 8^r * Product_{lengths i of runs of 1 in binary expansion of n} R(i), where r is the number of runs of 1 in the binary expansion of n and R(i) = A083424(i-1) = (5*4^(i-1)+(-2)^(i-1))/6. Note that row i of the table in A245562 lists the lengths of runs of 1 in binary expansion of i. Example: n=7 = 111 in binary, so r=1, i=3, R(3) = A083424(2) = 14, and so a(7) = 8^1*14 = 112. That is, this sequence is the Run Length Transform of A246030. - N. J. A. Sloane, Oct 04 2014

The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g. 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Aug 25 2014

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

a(n) = 2*a(n-1) + 11*a(n-2) + 6*a(n-3) with a(0)=1, a(1)=3 and a(2)=17.

a(n) = (-1)^(-n)*2^(n+1)/9 + ((49+17*sqrt(7))*A^(-n) + (49-17*sqrt(7))*B^(-n))/126 with A = (-2+sqrt(7))/3 and B = (-2-sqrt(7))/3.

Lim_{k->infinity} a(n+k)/a(k) = (-1)^(n+1)*A000244(n)/(A015530(n)*sqrt(7) - A108851(n)).

The following is a fairly simple explicit formula for a(n) as a function of n: a(n) = 8^(r-1) * Product_{lengths i of runs of 1 in binary expansion of n} R(i), where r is the number of runs of 1 in the binary expansion of n and R(i) = A083424(i-1) = (5*4^(i-1)+(-2)^(i-1))/6. Note that row i of the table in A245562 lists the lengths of runs of 1 in binary expansion of i. Example: n = 27 = 11011 in binary, there are two runs each of length 2, so r=1, R(2) = A083424(1) = 3, and so a(27) = 8^1*3*3 = 72. - N. J. A. Sloane, Aug 10 2014

Many 2-D cellular automata studied in the Toothpick paper (Applegate et al.) have a recursive formula for the general term in a typical block of 2^k terms (see Equations 2, 4, 5, 9, 10 12, 38, 39 of that paper). An analogous formula for the present sequence is the following.

Consider the block B_{k-1} containing terms a(2^(k-1)), a(2^(k-1)+1), ..., a(2^k-1). It is convenient to index the terms working backwards from the next, 2^k-th, term. For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then

(if j=0) a(2^k-2^r) = f(k-r-1),

(if j>0) a(2^k-2^r+j) = 8*f(k-r-1)*a(j),

where f(i) = A083424(i) = (5*4^i+(-2)^i)/6.

For example, here is block B_4, consisting of terms a(16)=a(31), so k=5:

n: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

a(n): 1 8 8 24 8 64 24 112 3 24 24 72 14 112 52 216

r: 4 4 4 4 4 4 4 4 3 3 3 3 2 2 1 0

j: 0 1 2 3 4 5 6 7 0 1 2 3 0 1 0 0

Then we have a(24) = a(32-8) = f(5-3-1) = f(1) = 3, illustrating the first equation, and a(21) = a(32-16+5) = 8*f(0)*a(5) = 8*1*8 = 64, illustrating the second equation.

See A245196 for a list of sequences produced by this type of recurrence.

This is an example of a class of sequences defined by the following recurrence.

We first choose a sequence G = [G(0), G(1), G(2), G(3), ...], which are the terms that will appear at the ends of the blocks: a(2^k-1) = G(k-1), and we also choose a parameter m (the "multiplier"). Then the recurrence (this defines a(1), a(2), a(3), ...) is:

a(2^k-2^r)=G(k-r-1) if 0 <= r <= k-1, a(2^k-2^r+j)=m*a(j)*G(k-r-1) if 2 <= r <= k-1, 1 <= j < 2^r-1.

To help apply the recurrence, here are the values of k,r,j for the first few values of n (if n=2^k-2^r we set j=0, although it is not used):

n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

k: 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4

r: 0 1 0 2 2 1 0 3 3 3 3 2 2 1 0

j: 0 0 0 0 1 0 0 0 1 2 3 0 1 0 0

--------------------------------------------------

n: 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

k: 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

r: 4 4 4 4 4 4 4 4 3 3 3 3 2 2 1 0

j: 0 1 2 3 4 5 6 7 0 1 2 3 0 1 0 0

--------------------------------------------------

In the present example G(n) = wt(n) and m=1.

a(n) = (5*5^n + (-1)^n)/6.

G.f.: 1/((1+x)*(1-5x)).

E.g.f.: (5*exp(5x) + exp(-x))/6.

a(n) = Sum_{k=0..n} C(n-k,k)*4^(n-2k)*5^k. - Paul Barry, Jul 29 2004

a(n) = A015531(n+1). - R. J. Mathar, Sep 17 2008

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

The entries may be arranged into blocks of sizes 1,2,4,8,...:

B_0: 1,

B_1: 1, 2,

B_2: 1, 1, 2, 4,

B_3: 1, 1, 1, 2, 2, 2, 4, 8,

B_4: 1, 1, 1, 2, 1, 1, 2, 4, 2, 2, 2, 4, 4, 4, 8, 16,

B_5: 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 1, 2, 2, 2, 4, 8, 2, 2, 2, 4, 2, 2, 4, 8, 4, 4, 4, 8, 8, 8, 16, 32,

...

Consider the block B_{k-1} containing terms a(2^(k-1)), a(2^(k-1)+1), ..., a(2^k-1). It is convenient to index the terms working backwards from the next, 2^k-th, term. For n in the range 2^(k-1) <= n < 2^k, write n = 2^k-2^r+j, with 0 <= r <= k-1 and 0 <= j < 2^(r-1), and j=0 if r=0. Then

(if j=0) a(2^k-2^r) = 2^(k-r-1),

(if j>0) a(2^k-2^r+j) = 2^(k-r-1)*a(j).

a(n) = A162510(A005940(1+n)). - Antti Karttunen, Oct 29 2016

From Robert Israel, Nov 02 2016: (Start)

a(2*k) = a(k).

a(4*k+1) = a(k).

a(4*k+3) = 2*a(2*k+1).

G.f. g(x) satisfies g(x) = x + (2*x+1)*g(x^2) - x*g(x^4). (End)

Also, a(n) = Sum_{k=0..floor(n/2)} ((binomial(n,2k)*binomial(n,k)) mod 2). - Chai Wah Wu, Oct 19 2016 and Robert Israel, Nov 04 2016. For proof, see the article by Chai Wah Wu, Sums of products of binomial coefficients mod 2 and run length transforms of sequences, arXiv:1610.06166, or the Robert Israel link.

a(0)=1, a(1)=8; thereafter a(n)=2*a(n-1)+8*a(n-2).

G.f.: (1+6*x)/(1-2*x-8*x^2).

a(n) = A001045(n+2)^2 - A001045(n)^2. - J. Conrad, Apr 05 2023