



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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, 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^(r1) * 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(i1) = (5*4^(i1)+(2)^(i1))/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 2D 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_{k1} containing terms a(2^(k1)), a(2^(k1)+1), ..., a(2^k1). It is convenient to index the terms working backwards from the next, 2^kth, term. For n in the range 2^(k1) <= n < 2^k, write n = 2^k2^r+j, with 0 <= r <= k1 and 0 <= j < 2^(r1), and j=0 if r=0. Then
(if j=0) a(2^k2^r) = f(kr1),
(if j>0) a(2^k2^r+j) = 8*f(kr1)*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(328) = f(531) = f(1) = 3, illustrating the first equation, and a(21) = a(3216+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 oneeighth 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((n1)/2)+R(n2)
else 8*R((n1)/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] (* JeanFranç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: A130300 A065451 A178148 * A054506 A101026 A055249
Adjacent sequences: A245177 A245178 A245179 * A245181 A245182 A245183


KEYWORD

nonn,tabf


AUTHOR

N. J. A. Sloane, Jul 16 2014


STATUS

approved



