OFFSET
1,2
COMMENTS
As the Sierpinski triangle is doubled in size by 2 copies of rows 0..2^k-1 making new rows 2^k .. 2^(k+1)-1, the terms of this sequence can be constructed in batches by doubling each of the first 2^k terms to obtain the next 2^k terms, the last of which is then augmented by 1.
Define the k-th batch of terms to be the 2^(k-1) consecutive terms a(2^(k-1)+1) .. a(2^k). Start with a(1) = 1. Then, for k = 0, 1, 2, 3, ..., the (k+1)st batch of terms is computed using the 2^k terms from the first k batches as follows: a(2^k+j) = 2*a(j) for j = 1..2^k - 1, and a(2^(k+1)) = 2*a(2^k) + 1.
For any integers m > 0 and k >= 0, a(n) = 2^m - 2^k first occurs at n = 2^m - 2^(m-k-1). (All terms take the form 2^m - 2^k for some m,k.)
a(n) is also the number of consecutive odd binomial coefficients in the (2n-1)-th row of Pascal's triangle.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..16384
Raphael S. Ner, Graph of the sequence.
Wikipedia, Sierpinski triangle.
FORMULA
a(n) = Sum_{i=0..2n-1} (binomial(2n-1,i) mod 2) * (binomial(2n-1,i+1) mod 2)).
a(n) = 2^(wt(n-1)+1) - 2^(wt(n)-1) where wt(n) = A000120(n).
a(n) = 2^(k+1) - 1 if n = 2^k, a(n) = 2*a(n-m) otherwise, where m = 2^floor(log_2(n)). - Jon E. Schoenfield, Sep 10 2022
From Alois P. Heinz, Jul 05 2023: (Start)
a(2*n+1) = A001316(n) for n>=0.
a(n) mod 2 = A209229(n). (End)
EXAMPLE
The first 4 terms of the sequence with the Sierpinski triangle:
^
/ \
/___\
/ \ / \
---1----------------------------- /___o___\
/ \ / \
/___\ /___\
/ \ / \ / \ / \
---3------------------------- /___o___o___o___\
/ \ / \
/___\ /___\
/ \ / \ / \ / \
---2--------------------- /___o___\ /___o___\
/ \ / \ / \ / \
/___\ /___\ /___\ /___\
/ \ / \ / \ / \ / \ / \ / \ / \
---7----------------- /___o___o___o___o___o___o___o___\
.
(The o symbols emphasize downward-pointing vertices of the small triangles; the number to the left of each row is the number of o symbols in it.)
a(n) is the number of o symbols in the n-th tagged line. A similar counting of upwards-pointing triangles leads to A001316.
MAPLE
a:= proc(n) option remember; (t->
`if`(t=0, 2*n-1, 2*a(t)))(n-2^ilog2(n))
end:
seq(a(n), n=1..100); # Alois P. Heinz, Jul 05 2023
MATHEMATICA
With[{wt = DigitCount[Range[0, 80], 2, 1]}, 2^(Most[wt] + 1) - 2^(Rest[wt] - 1)] (* Amiram Eldar, Jul 02 2023 *)
PROG
(PARI) a(n) = my(k=valuation(n, 2)); if (n==2^k, 2^(k+1) - 1, 2*a(n-2^logint(n, 2))); \\ Michel Marcus, Jun 20 2023
CROSSREFS
KEYWORD
AUTHOR
Raphael S. Ner, Jun 12 2023
STATUS
approved