A245180 - OEIS

%I #71 Feb 24 2021 02:48:19

%S 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 14,112,52,216,1,8,8,24,8,64,24,112,8,64,64,192,24,192,112,416,3,24,

%U 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 A160239(n)/8.

%H N. J. A. Sloane, <a href="/A245180/b245180.txt">Table of n, a(n) for n = 1..16383</a>

%H 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 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 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 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 (if j=0) a(2^k-2^r) = f(k-r-1),

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

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

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

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

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

%F r:    4  4  4  4  4  4  4  4  3  3  3  3  2   2  1  0

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

%F 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 See A245196 for a list of sequences produced by this type of recurrence.

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

%e B_0: 1,

%e B_1: 1, 3,

%e B_2: 1, 8, 3, 14,

%e B_3: 1, 8, 8, 24, 3, 24, 14, 52,

%e B_4: 1, 8, 8, 24, 8, 64, 24, 112, 3, 24, 24, 72, 14, 112, 52, 216,

%e 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 ...

%e The first half of each block is equal to 1 followed by 8 times an initial segment of the sequence itself.

%e The next quarter of each block consists of 3 times (1 followed by 8 times an initial segment of the sequence itself).

%e The next one-eighth of each block consists of 14 times (1 followed by 8 times an initial segment of the sequence itself).

%e And so on, the successive multipliers 1,3,14,52,... being given by A083424.

%e 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 Consider for example the 4th block,

%e [1, 8, 8, 24, 8, 64, 24, 112; 3, 24, 24, 72; 14, 112, 52, 216].

%e 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 The final entries in the blocks give A083424.

%e See also the formula section.

%e .

%e From _Omar E. Pol_, Mar 18 2015: (Start)

%e Also, the sequence can be written as an irregular tetrahedron T(s,r,k) as shown below:

%e 1;

%e ..

%e 1;

%e 3;

%e ........

%e 1,    8;

%e 3;

%e 14;

%e ................

%e 1,    8,  8, 24;

%e 3,   24;

%e 14;

%e 52;

%e ..................................

%e 1,    8,  8, 24,  8,  64, 24, 112;

%e 3,   24, 24, 72;

%e 14, 112;

%e 52;

%e 216;

%e .....................................................................

%e 1,    8,  8, 24,  8,  64, 24, 112, 8, 64, 64, 192, 24, 192, 112, 416;

%e 3,   24, 24, 72, 24, 192, 72, 336;

%e 14, 112,112,336;

%e 52, 416;

%e 216;

%e 848;

%e ...

%e Note that T(s,r,k) = T(s+1,r,k).

%e (End)

%p R:=proc(n) option remember;

%p if n=1 then 1

%p elif (n mod 2) = 0 then R(n/2)

%p elif (n mod 4) = 3 then 2*R((n-1)/2)+R(n-2)

%p else 8*R((n-1)/4); fi; end;

%p [seq(R(n),n=1..200)];

%t 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 Array[R, 200] (* _Jean-François Alcover_, Nov 16 2017, translated from Maple *)

%o (Haskell)

%o a245180 = flip div 8 . a160239  -- _Reinhard Zumkeller_, Feb 13 2015

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

%Y See A245181 for the numbers that appear.

%K nonn,tabf

%O 1,3

%A _N. J. A. Sloane_, Jul 16 2014