0,2

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.

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

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

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

.

(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

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

Omar E. Pol, Aug 22 2013

approved