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
Examples
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)
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
Crossrefs
Programs
-
Haskell
a245180 = flip div 8 . a160239 -- Reinhard Zumkeller, Feb 13 2015
-
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 *)
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.