cp's OEIS Frontend

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

%I A228366 #25 Jul 15 2022 02:31:53
%S A228366 0,2,6,8,15,17,21,23,35,37,41,43,50,52,56,58,79,81,85,87,94,96,100,
%T A228366 102,114,116,120,122,129,131,135,137,175,177,181,183,190,192,196,198,
%U A228366 210,212,216,218,225,227,231,233,254,256,260,262,269,271,275
%N A228366 Toothpick sequence from a diagram of compositions of the positive integers (see Comments lines for definition).
%C A228366 In order to construct this sequence we use the following rules:
%C A228366 We start in the first quadrant of the square grid with no toothpicks, so a(0) = 0.
%C A228366 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.
%C A228366 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.
%C A228366 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.
%C A228366 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.
%H A228366 N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>
%H A228366 <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>
%F A228366 a(n) = sum_{k=1..n} (A001511(k) + A006519(k)), n >= 1.
%F A228366 a(n) = A005187(n) + A065120(n-1), n >= 1.
%F A228366 a(n) = A228370(2n).
%e A228366 Illustration of initial terms (n = 1..8):
%e A228366 .                                                _ _ _ _
%e A228366 .                                        _       _      |
%e A228366 .                                _ _     _|_     _|_    |
%e A228366 .                        _       _  |    _  |    _  |   |
%e A228366 .                _ _ _   _|_ _   _|_|_   _|_|_   _|_|_  |
%e A228366 .          _     _    |  _    |  _    |  _    |  _    | |
%e A228366 .    _ _   _|_   _|_  |  _|_  |  _|_  |  _|_  |  _|_  | |
%e A228366 ._   _  |  _  |  _  | |  _  | |  _  | |  _  | |  _  | | |
%e A228366 . |   | |   | |   | | |   | | |   | | |   | | |   | | | |
%e A228366 .
%e A228366 .2    6     8      15      17      21      23       35
%e A228366 .
%e A228366 After 16 stages there are 79 toothpicks in the structure which represents the compositions of 5 in colexicographic order as shown below:
%e A228366 -------------------------------
%e A228366 n     Diagram      Composition
%e A228366 -------------------------------
%e A228366 .     _ _ _ _ _
%e A228366 16    _        |   5
%e A228366 15    _|_      |   1+4
%e A228366 14    _  |     |   2+3
%e A228366 13    _|_|_    |   1+1+3
%e A228366 12    _    |   |   3+2
%e A228366 11    _|_  |   |   1+2+2
%e A228366 10    _  | |   |   2+1+2
%e A228366 9     _|_|_|_  |   1+1+1+2
%e A228366 8     _      | |   4+1
%e A228366 7     _|_    | |   1+3+1
%e A228366 6     _  |   | |   2+2+1
%e A228366 5     _|_|_  | |   1+1+2+1
%e A228366 4     _    | | |   3+1+1
%e A228366 3     _|_  | | |   1+2+1+1
%e A228366 2     _  | | | |   2+1+1+1
%e A228366 1      | | | | |   1+1+1+1+1
%e A228366 .
%o A228366 (Python)
%o A228366 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
%Y A228366 Cf. A001511, A005187, A006519, A011782, A001792, A065120, A139250, A228367, A228370, A228371, A228525.
%K A228366 nonn
%O A228366 0,2
%A A228366 _Omar E. Pol_, Aug 22 2013