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

0, 1, 2, 4, 6, 7, 8, 11, 15, 16, 17, 19, 21, 22, 23, 27, 35, 36, 37, 39, 41, 42, 43, 46, 50, 51, 52, 54, 56, 57, 58, 63, 79, 80, 81, 83, 85, 86, 87, 90, 94, 95, 96, 98, 100, 101, 102, 106, 114, 115, 116, 118, 120, 121, 122, 125, 129, 130, 131, 133, 135, 136, 137, 143, 175

Offset: 0

Author

Omar E. Pol, Aug 21 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.

If n is odd then 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+1)/2) 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.

If n is even then at stage n 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.

Note that the number of toothpick of added at stage (n+1)/2 in horizontal direction is also A001511(n) and the number of toothpicks added at stage n/2 in vertical direction is also A006519(n).

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

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.

The equivalent sequence for partitions is A225600.

Examples

			For n = 32 the diagram represents the 16 compositions of 5. The structure has 79 toothpicks, so a(32) = 79. Note that the k-th horizontal line segment has length A001511(k) equals the largest part of the k-th region, and the k-th vertical line segment has length A006519(k) equals the number of parts of the k-th region.
----------------------------------------------------------
.                                    Triangle
Compositions                  of compositions (rows)
of 5          Diagram          and regions (columns)
----------------------------------------------------------
.            _ _ _ _ _
5            _        |                                 5
1+4          _|_      |                               1 4
2+3          _  |     |                             2   3
1+1+3        _|_|_    |                           1 1   3
3+2          _    |   |                         3       2
1+2+2        _|_  |   |                       1 2       2
2+1+2        _  | |   |                     2   1       2
1+1+1+2      _|_|_|_  |                   1 1   1       2
4+1          _      | |                 4               1
1+3+1        _|_    | |               1 3               1
2+2+1        _  |   | |             2   2               1
1+1+2+1      _|_|_  | |           1 1   2               1
3+1+1        _    | | |         3       1               1
1+2+1+1      _|_  | | |       1 2       1               1
2+1+1+1      _  | | | |     2   1       1               1
1+1+1+1+1     | | | | |   1 1   1       1               1
.
Illustration of initial terms (n = 1..16):
.
.                                   _        _
.                   _ _    _ _      _ _      _|_
.       _     _     _      _  |     _  |     _  |
.              |     |      | |      | |      | |
.
.       1      2     4      6        7        8
.
.
.                                            _ _
.                        _         _         _
.     _ _ _    _ _ _     _ _ _     _|_ _     _|_ _
.     _        _    |    _    |    _    |    _    |
.     _|_      _|_  |    _|_  |    _|_  |    _|_  |
.     _  |     _  | |    _  | |    _  | |    _  | |
.      | |      | | |     | | |     | | |     | | |
.
.       11       15        16        17        19
.
.
.                                _ _ _ _    _ _ _ _
.             _        _         _          _      |
.    _ _      _ _      _|_       _|_        _|_    |
.    _  |     _  |     _  |      _  |       _  |   |
.    _|_|_    _|_|_    _|_|_     _|_|_      _|_|_  |
.    _    |   _    |   _    |    _    |     _    | |
.    _|_  |   _|_  |   _|_  |    _|_  |     _|_  | |
.    _  | |   _  | |   _  | |    _  | |     _  | | |
.     | | |    | | |    | | |     | | |      | | | |
.
.      21       22       23        27          35
.
		

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, A006520, A011782, A139250, A187816, A187818, A206437, A225600, A228350, A228351, A228366, A228367, A228368, A228371, A228525, A228526.

Programs

Python

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

Formula

a(n) = sum_{k=1..n} A228371(k), n >= 1.

a(2n-1) = A005187(n) + A006520(n+1) - A006519(n), n >= 1.

a(2n) = A005187(n) + A006520(n+1), n >= 1.