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

Author

Omar E. Pol, Aug 22 2013

Keywords

• nonn

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.

Examples

			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
.
		

Links

• N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
• Index entries for sequences related to toothpick sequences

Crossrefs

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

Programs

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

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).