A245180 A160239(n)/8.

1, 1, 3, 1, 8, 3, 14, 1, 8, 8, 24, 3, 24, 14, 52, 1, 8, 8, 24, 8, 64, 24, 112, 3, 24, 24, 72, 14, 112, 52, 216, 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416, 3, 24, 24, 72, 24, 192, 72, 336, 14, 112, 112, 336, 52, 416, 216, 848, 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192

Offset

1,3

Links

N. J. A. Sloane, Table of n, a(n) for n = 1..16383

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.], which is also available at arXiv:1004.3036v2

Formula

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.

Example

The entries may be arranged into blocks of sizes 1,2,4,8,...:
B_0: 1,
B_1: 1, 3,
B_2: 1, 8, 3, 14,
B_3: 1, 8, 8, 24, 3, 24, 14, 52,
B_4: 1, 8, 8, 24, 8, 64, 24, 112, 3, 24, 24, 72, 14, 112, 52, 216,
B_5: 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416, 3, 24, 24, 72, 24, 192, 72, 336, 14, 112, 112, 336, 52, 416, 216, 848,
...
The first half of each block is equal to 1 followed by 8 times an initial segment of the sequence itself.
The next quarter of each block consists of 3 times (1 followed by 8 times an initial segment of the sequence itself).
The next one-eighth of each block consists of 14 times (1 followed by 8 times an initial segment of the sequence itself).
And so on, the successive multipliers 1,3,14,52,... being given by A083424.
Also, the final quarter of any block consists of the twice the last half of the previous block added to eight times the full block before that.
Consider for example the 4th block,
[1, 8, 8, 24, 8, 64, 24, 112; 3, 24, 24, 72; 14, 112, 52, 216].
This is [1 8*(1,1,3,1,8,3,14); 3*(1 8*(1,1,3)); 2*(3,24,14,52)+8*(1,8,3,14)].
The final entries in the blocks give A083424.
See also the formula section.
.
From Omar E. Pol, Mar 18 2015: (Start)
Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
1;
..
1;
3;
........
1,    8;
3;
14;
................
1,    8,  8, 24;
3,   24;
14;
52;
..................................
1,    8,  8, 24,  8,  64, 24, 112;
3,   24, 24, 72;
14, 112;
52;
216;
.....................................................................
1,    8,  8, 24,  8,  64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416;
3,   24, 24, 72, 24, 192, 72, 336;
14, 112,112,336;
52, 416;
216;
848;
...
Note that T(s,r,k) = T(s+1,r,k).
(End)

Maple

R:=proc(n) option remember;
if n=1 then 1
elif (n mod 2) = 0 then R(n/2)
elif (n mod 4) = 3 then 2*R((n-1)/2)+R(n-2)
else 8*R((n-1)/4); fi; end;
[seq(R(n), n=1..200)];

Mathematica

R[n_] := R[n] = Which[n == 1, 1, Mod[n, 2] == 0, R[n/2], Mod[n, 4] == 3, 2*R[(n - 1)/2] + R[n - 2], True, 8*R[(n - 1)/4] ];
Array[R, 200] (* Jean-François Alcover, Nov 16 2017, translated from Maple *)

Prog

(Haskell)
a245180 = flip div 8 . a160239  -- Reinhard Zumkeller, Feb 13 2015

Crossrefs

Cf. A160239, A083424, A245190, A245195, A245196, A245562, A245540 (partial sums).

See A245181 for the numbers that appear.

Sequence in context: A065451 A178148 A337681 * A054506 A101026 A055249

Adjacent sequences: A245177 A245178 A245179 * A245181 A245182 A245183

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jul 16 2014

Status

approved