A228366 Toothpick sequence from a diagram of compositions of the positive integers (see Comments lines for definition).

0, 2, 6, 8, 15, 17, 21, 23, 35, 37, 41, 43, 50, 52, 56, 58, 79, 81, 85, 87, 94, 96, 100, 102, 114, 116, 120, 122, 129, 131, 135, 137, 175, 177, 181, 183, 190, 192, 196, 198, 210, 212, 216, 218, 225, 227, 231, 233, 254, 256, 260, 262, 269, 271, 275

Offset

0,2

Comments

In order to construct this sequence we use the following rules:

We start in the first quadrant of the square grid with no toothpicks, so a(0) = 0.

At stage n we place the smallest possible number of toothpicks of length 1 connected by their endpoints in horizontal direction starting from the grid point (0, n) such that the x-coordinate of the exposed endpoint of the last toothpick is not equal to the x-coordinate of any outer corner of the structure. Then we place toothpicks of length 1 connected by their endpoints in vertical direction, starting from the exposed toothpick endpoint, downward up to touch the structure or up to touch the x-axis.

The sequence gives the number of toothpicks after n stages. A228367 (the first differences) gives the number of toothpicks added at the n-th stage.

Note that the number of toothpick of added at n-th stage in horizontal direction is also A001511(n) and the number of toothpicks added at n-th stage in vertical direction is also A006519(n). Also counting both the x-axis and the y-axis we have that A001511(n) is also the largest part of the n-th region of the diagram and A006519(n) is also the number of parts of the n-th region of the diagram.

After 2^k stages a new section of the structure is completed, so the structure can be interpreted as a diagram of the 2^(k-1) compositions of k in colexicographic order, if k >= 1 (see A228525). The infinite diagram can be interpreted as a table of compositions of the positive integers.

Links

Table of n, a(n) for n=0..54.

N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Index entries for sequences related to toothpick sequences

Formula

a(n) = sum_{k=1..n} (A001511(k) + A006519(k)), n >= 1.

a(n) = A005187(n) + A065120(n-1), n >= 1.

a(n) = A228370(2n).

Example

Illustration of initial terms (n = 1..8):
.                                                _ _ _ _
.                                        _       _      |
.                                _ _     _|_     _|_    |
.                        _       _  |    _  |    _  |   |
.                _ _ _   _|_ _   _|_|_   _|_|_   _|_|_  |
.          _     _    |  _    |  _    |  _    |  _    | |
.    _ _   _|_   _|_  |  _|_  |  _|_  |  _|_  |  _|_  | |
._   _  |  _  |  _  | |  _  | |  _  | |  _  | |  _  | | |
. |   | |   | |   | | |   | | |   | | |   | | |   | | | |
.
.2    6     8      15      17      21      23       35
.
After 16 stages there are 79 toothpicks in the structure which represents the compositions of 5 in colexicographic order as shown below:
-------------------------------
n     Diagram      Composition
-------------------------------
.     _ _ _ _ _
16    _        |   5
15    _|_      |   1+4
14    _  |     |   2+3
13    _|_|_    |   1+1+3
12    _    |   |   3+2
11    _|_  |   |   1+2+2
10    _  | |   |   2+1+2
9     _|_|_|_  |   1+1+1+2
8     _      | |   4+1
7     _|_    | |   1+3+1
6     _  |   | |   2+2+1
5     _|_|_  | |   1+1+2+1
4     _    | | |   3+1+1
3     _|_  | | |   1+2+1+1
2     _  | | | |   2+1+1+1
1      | | | | |   1+1+1+1+1
.

Prog

(Python)
def A228366(n): return sum(((m:=(i>>1)+1)&-m).bit_length() if i&1 else (m:=i>>1)&-m for i in range(1, 2*n+1)) # Chai Wah Wu, Jul 15 2022

Crossrefs

Cf. A001511, A005187, A006519, A011782, A001792, A065120, A139250, A228367, A228370, A228371, A228525.

Sequence in context: A067795 A212353 A029933 * A345958 A128913 A093005

Adjacent sequences: A228363 A228364 A228365 * A228367 A228368 A228369

Keyword

nonn

Author

Omar E. Pol, Aug 22 2013

Status

approved