OFFSET
0,2
COMMENTS
Partial sums of A048883. - David Applegate, Jun 11 2009
From Gary W. Adamson, Aug 26 2016: (Start)
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:
1, 0, 0, 0, 0, 0, ...
4, 0, 0, 0, 0, 0, ...
3, 1, 0, 0, 0, 0, ...
0, 4, 0, 0, 0, 0, ...
0, 3, 1, 0, 0, 0, ...
0, 0, 4, 0, 0, 0, ...
0, 0, 3, 1, 0, 0, ...
...
The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
David Applegate, The movie version
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 31-32.
Tanya Khovanova and Joshua Xiong, Nim Fractals, arXiv:1405.594291 [math.CO], 2014 and J. Int. Seq. 17 (2014) # 14.7.8.
D. E. Knuth, Problem 11320 Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
Omar E. Pol, Illustration of initial terms: Fig. 1. Neighbors of the vertices, Fig. 2. Overlapping squares, Fig. 3. One-step bishop, (Nov 08 2009)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Mike Warburton, Ulam-Warburton Automaton - Counting Cells with Quadratics, arXiv:1901.10565 [math.CO], 2019.
FORMULA
With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
a(n) = (A147562(n+1) - 1)*3/4 + 1. - Omar E. Pol, Nov 08 2009
a(n) = A160410(n+1)/4. - Omar E. Pol, Nov 12 2009
Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
r(x)* r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010
For asymptotics see the discussion in the comments in A006046. - N. J. A. Sloane, Mar 11 2021
a(n) = Sum_{k=0..floor(log_2(n+1))} 3^k * A360189(n,k). - Alois P. Heinz, Mar 06 2023
a(n) = msb^2 + 3*a(n-msb), where msb = A053644(n). - Stefan Pochmann, Mar 15 2023
MAPLE
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
MATHEMATICA
f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* Robert G. Wilson v, Jun 28 2010 *)
PROG
(Haskell)
a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
-- Reinhard Zumkeller, Apr 18 2012
(Python)
def a(n): # formula version, n=10^10000 takes ~1 second
if n == 0:
return 1
msb = 1 << (n.bit_length() - 1)
return msb**2 + 3 * a(n-msb) # Stefan Pochmann, Mar 15 2023
(Python)
def a(n): # optimized, n=10^50000 takes ~1 second
n += 1
total = 0
power3 = 1
while n:
log = n.bit_length() - 1
total += power3 << (2*log)
n -= 1 << log
power3 *= 3
return total # Stefan Pochmann, Mar 15 2023
CROSSREFS
KEYWORD
AUTHOR
N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007
EXTENSIONS
Simpler definition (and new offset) from David Applegate, Jun 11 2009
Lower limit of sum in definition changed from 1 to 0 by Robert G. Wilson v, Jun 28 2010
STATUS
approved