|
%I #80 Mar 06 2023 17:20:29
%S 0,1,5,9,25,29,45,61,125,129,145,161,225,241,305,369,625,629,645,661,
%T 725,741,805,869,1125,1141,1205,1269,1525,1589,1845,2101,3125,3129,
%U 3145,3161,3225,3241,3305,3369,3625,3641,3705,3769,4025,4089,4345,4601,5625
%N a(0) = 0, a(1) = 1; a(n) = max { 4*a(k) + a(n-k) | 1 <= k <= n/2 }, for n > 1.
%C Equivalently, a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(0)=0, a(1)=1, for (r,s) = (1,4). - _N. J. A. Sloane_, Feb 16 2016
%C A 5-divide version of A084230.
%C Zero together with the partial sums of A102376. - _Omar E. Pol_, May 05 2010
%C Also, total number of cubic ON cells after n generations in a three-dimensional cellular automaton in which A102376(n-1) gives the number of cubic ON cells in the n-th level of the structure starting from the top. An ON cell remains ON forever. The structure looks like an irregular stepped pyramid, with n >= 1. - _Omar E. Pol_, Feb 13 2015
%C From _Gary W. Adamson_, Aug 27 2016: (Start)
%C The formula of Mar 26 2010 is equivalent to lim_{k->infinity} M^k of the following production matrix M:
%C 1, 0, 0, 0, 0, 0, ...
%C 5, 0, 0, 0, 0, 0, ...
%C 4, 1, 0, 0, 0, 0, ...
%C 0, 5, 0, 0, 0, 0, ...
%C 0, 4, 1, 0, 0, 0, ...
%C 0, 0, 5, 0, 0, 0, ...
%C 0, 0, 4, 1, 0, 0, ...
%C 0, 0, 0, 5, 0, 0, ...
%C ...
%C The sequence with offset 1 divided by its aerated variant is (1, 5, 4, 0, 0, 0, ...). (End)
%H Reinhard Zumkeller, <a href="/A116520/b116520.txt">Table of n, a(n) for n = 0..10000</a>
%H K.-N. Chang and S.-C. Tsai, <a href="http://dx.doi.org/10.1016/S0020-0190(00)00076-4">Exact solution of a minimal recurrence</a>, Inform. Process. Lett. 75 (2000), 61-64.
%H H. Harborth, <a href="http://dx.doi.org/10.1090/S0002-9939-1977-0429714-1">Number of Odd Binomial Coefficients</a>, Proc. Amer. Math. Soc. 62, 19-22, 1977.
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 32.
%H D. E. Knuth, <a href="http://www.jstor.org/stable/27642339">Problem 11320</a>, The American Mathematical Monthly, Vol. 114, No. 9 (Nov., 2007), p. 835.
%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Stolarsky-HarborthConstant.html">Stolarsky-Harborth Constant</a>
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F a(0) = 1, a(1) = 1; thereafter a(2n) = 5a(n) and a(2n+1) = 4a(n) + a(n+1).
%F Let r(x) = (1 + 5x + 4x^2). Then (1 + 5x + 9x^2 + 25x^3 + ...) = r(x) * r(x^2) * r(x^4) * r(x^8) * ... . - _Gary W. Adamson_, Mar 26 2010
%F a(n) = Sum_{k=0..n-1} 4^wt(k), where wt = A000120. - _Mike Warburton_, Mar 14 2019
%F a(n) = Sum_{k=0..floor(log_2(n))} 4^k*A360189(n-1,k). - _Alois P. Heinz_, Mar 06 2023
%p a:=proc(n) if n=0 then 0 elif n=1 then 1 elif n mod 2 = 0 then 5*a(n/2) else 4*a((n-1)/2)+a((n+1)/2) fi end: seq(a(n),n=0..52);
%t b[0] := 0 b[1] := 1 b[n_?EvenQ] := b[n] = 5*b[n/2] b[n_?OddQ] := b[n] = 4*b[(n - 1)/2] + b[(n + 1)/2] a = Table[b[n], {n, 1, 25}]
%o (Haskell)
%o import Data.List (transpose)
%o a116520 n = a116520_list !! n
%o a116520_list = 0 : zs where
%o zs = 1 : (concat $ transpose
%o [zipWith (+) vs zs, zipWith (+) vs $ tail zs])
%o where vs = map (* 4) zs
%o -- _Reinhard Zumkeller_, Apr 18 2012
%Y Cf. A000120, A006046, A077465, A130665, A130667, A102376, A360189.
%Y Sequences of the form a(n) = r*a(ceiling(n/2)) + s*a(floor(n/2)), a(1)=1, for (r,s) = (1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1): A000027, A006046, A064194, A130665, A073121, A268524, A116520, A268525, A268526, A268527.
%K nonn,look
%O 0,3
%A _Roger L. Bagula_, Mar 15 2006
%E Edited by _N. J. A. Sloane_, Apr 16 2006, Jul 02 2008
|
