cp's OEIS Frontend

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

%I A130665 #80 Mar 16 2023 04:49:03
%S A130665 1,4,7,16,19,28,37,64,67,76,85,112,121,148,175,256,259,268,277,304,
%T A130665 313,340,367,448,457,484,511,592,619,700,781,1024,1027,1036,1045,1072,
%U A130665 1081,1108,1135,1216,1225,1252,1279,1360,1387,1468,1549,1792,1801,1828,1855
%N A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().
%C A130665 Partial sums of A048883. - _David Applegate_, Jun 11 2009
%C A130665 From _Gary W. Adamson_, Aug 26 2016: (Start)
%C A130665 The formula of Mar 26 2010 is equivalent to the left-shifted vector of matrix powers (lim_{k->infinity} M^k), of the production matrix M:
%C A130665   1, 0, 0, 0, 0, 0, ...
%C A130665   4, 0, 0, 0, 0, 0, ...
%C A130665   3, 1, 0, 0, 0, 0, ...
%C A130665   0, 4, 0, 0, 0, 0, ...
%C A130665   0, 3, 1, 0, 0, 0, ...
%C A130665   0, 0, 4, 0, 0, 0, ...
%C A130665   0, 0, 3, 1, 0, 0, ...
%C A130665   ...
%C A130665 The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)
%H A130665 Reinhard Zumkeller, <a href="/A130665/b130665.txt">Table of n, a(n) for n = 0..10000</a>
%H A130665 David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>
%H A130665 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, 31-32.
%H A130665 Tanya Khovanova and Joshua Xiong, <a href="http://arxiv.org/abs/1405.5942">Nim Fractals</a>, arXiv:1405.594291 [math.CO], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Khovanova/khova6.html">J. Int. Seq. 17 (2014) # 14.7.8</a>.
%H A130665 D. E. Knuth, <a href="http://www.jstor.org/stable/27642339">Problem 11320</a> Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
%H A130665 Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/polca011">Illustration of initial terms: Fig. 1. Neighbors of the vertices</a>, <a href="http://www.polprimos.com/imagenespub/polca013">Fig. 2. Overlapping squares</a>, <a href="http://www.polprimos.com/imagenespub/polca015">Fig. 3. One-step bishop</a>, (Nov 08 2009)
%H A130665 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 A130665 Mike Warburton, <a href="https://arxiv.org/abs/1901.10565">Ulam-Warburton Automaton - Counting Cells with Quadratics</a>, arXiv:1901.10565 [math.CO], 2019.
%F A130665 With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
%F A130665 a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
%F A130665 a(n) = (A147562(n+1) - 1)*3/4 + 1. - _Omar E. Pol_, Nov 08 2009
%F A130665 a(n) = A160410(n+1)/4. - _Omar E. Pol_, Nov 12 2009
%F A130665 Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
%F A130665 r(x)* r(x^2) * r(x^4) * r(x^8) * ... - _Gary W. Adamson_, Mar 26 2010
%F A130665 For asymptotics see the discussion in the comments in A006046. - _N. J. A. Sloane_, Mar 11 2021
%F A130665 a(n) = Sum_{k=0..floor(log_2(n+1))} 3^k * A360189(n,k). - _Alois P. Heinz_, Mar 06 2023
%F A130665 a(n) = msb^2 + 3*a(n-msb), where msb = A053644(n). - _Stefan Pochmann_, Mar 15 2023
%p A130665 u:=3; a[1]:=1; M:=30; for n from 1 to M do a[2*n] := (u+1)*a[n]; a[2*n+1] := u*a[n] + a[n+1]; od; t1:=[seq( a[n], n=1..2*M )]; # Gives sequence with a different offset
%t A130665 f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* _Robert G. Wilson v_, Jun 28 2010 *)
%o A130665 (Haskell)
%o A130665 a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
%o A130665 -- _Reinhard Zumkeller_, Apr 18 2012
%o A130665 (Python)
%o A130665 def a(n):  # formula version, n=10^10000 takes ~1 second
%o A130665     if n == 0:
%o A130665         return 1
%o A130665     msb = 1 << (n.bit_length() - 1)
%o A130665     return msb**2 + 3 * a(n-msb) # _Stefan Pochmann_, Mar 15 2023
%o A130665 (Python)
%o A130665 def a(n):  # optimized, n=10^50000 takes ~1 second
%o A130665     n += 1
%o A130665     total = 0
%o A130665     power3 = 1
%o A130665     while n:
%o A130665         log = n.bit_length() - 1
%o A130665         total += power3 << (2*log)
%o A130665         n -= 1 << log
%o A130665         power3 *= 3
%o A130665     return total # _Stefan Pochmann_, Mar 15 2023
%Y A130665 Cf. A000120, A006046 (Sum 2^wt(n)), A116520, A130667, A147562, A151920, A151922, A160410, A160412, A360189.
%K A130665 nonn,look,base
%O A130665 0,2
%A A130665 _N. J. A. Sloane_, based on a message from _Don Knuth_, Jun 23 2007
%E A130665 Simpler definition (and new offset) from _David Applegate_, Jun 11 2009
%E A130665 Lower limit of sum in definition changed from 1 to 0 by _Robert G. Wilson v_, Jun 28 2010