A361145 Number of downwards peaks in row 2n-1 of the Sierpinski triangle.

1, 3, 2, 7, 2, 6, 4, 15, 2, 6, 4, 14, 4, 12, 8, 31, 2, 6, 4, 14, 4, 12, 8, 30, 4, 12, 8, 28, 8, 24, 16, 63, 2, 6, 4, 14, 4, 12, 8, 30, 4, 12, 8, 28, 8, 24, 16, 62, 4, 12, 8, 28, 8, 24, 16, 60, 8, 24, 16, 56, 16, 48, 32, 127, 2, 6, 4, 14, 4, 12, 8, 30, 4, 12, 8, 28, 8, 24, 16, 62

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

Cf. A047999, A000120, A048881, A001316, A053645, A209229.

Sequence in context: A209639 A366161 A174238 * A175920 A200593 A249112

Adjacent sequences: A361142 A361143 A361144 * A361146 A361147 A361148

Keyword

nonn,easy,look

Author

Raphael S. Ner, Jun 12 2023

Status

approved