OFFSET
0,2
COMMENTS
Here J(k) = (2^k - (-1)^k)/3 are the Jacobsthal numbers.
a(n) is the total Jacobsthal weight of all base-3 words of length n, where each maximal block of nonzero digits of length k contributes a factor J(k).
Equivalently, if a base-3 word is replaced by its zero-support pattern in {0,1}^n, then a pattern with w 1's lifts to 2^w ternary words; a(n) is the resulting weighted sum over binary support patterns.
The classical binary Jacobsthal run-length-transform sequence is A071053.
More generally, a(n) is the total mass of the base-3 Jacobsthal run-length transform on the interval {0, ..., 3^n - 1}.
REFERENCES
N. J. A. Sloane, "On the Number of ON Cells in Cellular Automata", in Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham, Cambridge Univ. Press, 2018, pp. 13-38.
LINKS
Ahmet Caglar Saygili, Table of n, a(n) for n = 0..1000
D. Brod and A. Michalski, On Generalized Jacobsthal and Jacobsthal-Lucas Numbers, Ann. Math. Siles. 36 (2022), no. 2, 115-128.
S. Kropf and S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, Electron. J. Combin. 24 (2017), no. 1, Paper P1.60.
Index entries for linear recurrences with constant coefficients, signature (3,8,-8).
FORMULA
a(0) = 1, a(1) = 3, a(2) = 9; for n >= 3, a(n) = 3*a(n-1) + 8*a(n-2) - 8*a(n-3).
G.f.: (1 - 8*x^2)/(1 - 3*x - 8*x^2 + 8*x^3).
EXAMPLE
There are 27 base-3 words of length 3. The totals recurrence gives a(3) = a(2) + 2*J(1)*a(1) + 2^2*J(2)*a(0) + 2^3*J(3) = 9 + 2*1*3 + 4*1*1 + 8*3 = 43.
MATHEMATICA
LinearRecurrence[{3, 8, -8}, {1, 3, 9}, 30]
PROG
(Julia)
a(n) = begin
vals = BigInt[1, 3, 9]
while length(vals) <= n + 1
push!(vals, 3*vals[end] + 8*vals[end-1] - 8*vals[end-2])
end
vals[n + 1]
end
(Python)
def a(n):
vals = [1, 3, 9]
while len(vals) <= n:
vals.append(3*vals[-1] + 8*vals[-2] - 8*vals[-3])
return vals[n]
(PARI) first(nn)= if(nn<1, [], my(r=List([1, 3, 9])); for(i=#r+1, nn, listput(~r, 3*r[#r] + 8*(r[#r-1]-r[#r-2]))); Vec(r, nn)); \\ Ruud H.G. van Tol, Apr 22 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ahmet Caglar Saygili, Apr 15 2026
STATUS
approved