cp's OEIS Frontend

A245180 A160239(n)/8.

%I A245180 #71 Feb 24 2021 02:48:19
%S A245180 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,
%T A245180 14,112,52,216,1,8,8,24,8,64,24,112,8,64,64,192,24,192,112,416,3,24,
%U A245180 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
%N A245180 A160239(n)/8.
%H A245180 N. J. A. Sloane, <a href="/A245180/b245180.txt">Table of n, a(n) for n = 1..16383</a>
%H A245180 David Applegate, Omar E. Pol and N. J. A. Sloane, <a href="/A000695/a000695_1.pdf">The Toothpick Sequence and Other Sequences from Cellular Automata</a>, 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 <a href="http://arxiv.org/abs/1004.3036">arXiv:1004.3036v2</a>
%F A245180 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
%F A245180 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.
%F A245180 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
%F A245180 (if j=0) a(2^k-2^r) = f(k-r-1),
%F A245180 (if j>0) a(2^k-2^r+j) = 8*f(k-r-1)*a(j),
%F A245180 where f(i) = A083424(i) = (5*4^i+(-2)^i)/6.
%F A245180 For example, here is block B_4, consisting of terms a(16)=a(31), so k=5:
%F A245180 n:   16 17 18 19 20 21 22 23 24 25 26 27 28  29 30 31
%F A245180 a(n): 1  8  8 24  8 64 24 112 3 24 24 72 14 112 52 216
%F A245180 r:    4  4  4  4  4  4  4  4  3  3  3  3  2   2  1  0
%F A245180 j:    0  1  2  3  4  5  6  7  0  1  2  3  0   1  0  0
%F A245180 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.
%F A245180 See A245196 for a list of sequences produced by this type of recurrence.
%e A245180 The entries may be arranged into blocks of sizes 1,2,4,8,...:
%e A245180 B_0: 1,
%e A245180 B_1: 1, 3,
%e A245180 B_2: 1, 8, 3, 14,
%e A245180 B_3: 1, 8, 8, 24, 3, 24, 14, 52,
%e A245180 B_4: 1, 8, 8, 24, 8, 64, 24, 112, 3, 24, 24, 72, 14, 112, 52, 216,
%e A245180 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,
%e A245180 ...
%e A245180 The first half of each block is equal to 1 followed by 8 times an initial segment of the sequence itself.
%e A245180 The next quarter of each block consists of 3 times (1 followed by 8 times an initial segment of the sequence itself).
%e A245180 The next one-eighth of each block consists of 14 times (1 followed by 8 times an initial segment of the sequence itself).
%e A245180 And so on, the successive multipliers 1,3,14,52,... being given by A083424.
%e A245180 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.
%e A245180 Consider for example the 4th block,
%e A245180 [1, 8, 8, 24, 8, 64, 24, 112; 3, 24, 24, 72; 14, 112, 52, 216].
%e A245180 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)].
%e A245180 The final entries in the blocks give A083424.
%e A245180 See also the formula section.
%e A245180 .
%e A245180 From _Omar E. Pol_, Mar 18 2015: (Start)
%e A245180 Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:
%e A245180 1;
%e A245180 ..
%e A245180 1;
%e A245180 3;
%e A245180 ........
%e A245180 1,    8;
%e A245180 3;
%e A245180 14;
%e A245180 ................
%e A245180 1,    8,  8, 24;
%e A245180 3,   24;
%e A245180 14;
%e A245180 52;
%e A245180 ..................................
%e A245180 1,    8,  8, 24,  8,  64, 24, 112;
%e A245180 3,   24, 24, 72;
%e A245180 14, 112;
%e A245180 52;
%e A245180 216;
%e A245180 .....................................................................
%e A245180 1,    8,  8, 24,  8,  64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416;
%e A245180 3,   24, 24, 72, 24, 192, 72, 336;
%e A245180 14, 112,112,336;
%e A245180 52, 416;
%e A245180 216;
%e A245180 848;
%e A245180 ...
%e A245180 Note that T(s,r,k) = T(s+1,r,k).
%e A245180 (End)
%p A245180 R:=proc(n) option remember;
%p A245180 if n=1 then 1
%p A245180 elif (n mod 2) = 0 then R(n/2)
%p A245180 elif (n mod 4) = 3 then 2*R((n-1)/2)+R(n-2)
%p A245180 else 8*R((n-1)/4); fi; end;
%p A245180 [seq(R(n),n=1..200)];
%t A245180 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] ];
%t A245180 Array[R, 200] (* _Jean-François Alcover_, Nov 16 2017, translated from Maple *)
%o A245180 (Haskell)
%o A245180 a245180 = flip div 8 . a160239  -- _Reinhard Zumkeller_, Feb 13 2015
%Y A245180 Cf. A160239, A083424, A245190, A245195, A245196, A245562, A245540 (partial sums).
%Y A245180 See A245181 for the numbers that appear.
%K A245180 nonn,tabf
%O A245180 1,3
%A A245180 _N. J. A. Sloane_, Jul 16 2014