|
%I #33 Jul 14 2022 08:55:48
%S 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,
%T 51,52,54,56,57,58,63,79,80,81,83,85,86,87,90,94,95,96,98,100,101,102,
%U 106,114,115,116,118,120,121,122,125,129,130,131,133,135,136,137,143,175
%N Toothpick sequence from a diagram of compositions of the positive integers (see Comments lines for definition).
%C In order to construct this sequence we use the following rules:
%C We start in the first quadrant of the square grid with no toothpicks, so a(0) = 0.
%C 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.
%C 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.
%C 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).
%C 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.
%C 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.
%C The equivalent sequence for partitions is A225600.
%H 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 <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>
%F a(n) = sum_{k=1..n} A228371(k), n >= 1.
%F a(2n-1) = A005187(n) + A006520(n+1) - A006519(n), n >= 1.
%F a(2n) = A005187(n) + A006520(n+1), n >= 1.
%e 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.
%e ----------------------------------------------------------
%e . Triangle
%e Compositions of compositions (rows)
%e of 5 Diagram and regions (columns)
%e ----------------------------------------------------------
%e . _ _ _ _ _
%e 5 _ | 5
%e 1+4 _|_ | 1 4
%e 2+3 _ | | 2 3
%e 1+1+3 _|_|_ | 1 1 3
%e 3+2 _ | | 3 2
%e 1+2+2 _|_ | | 1 2 2
%e 2+1+2 _ | | | 2 1 2
%e 1+1+1+2 _|_|_|_ | 1 1 1 2
%e 4+1 _ | | 4 1
%e 1+3+1 _|_ | | 1 3 1
%e 2+2+1 _ | | | 2 2 1
%e 1+1+2+1 _|_|_ | | 1 1 2 1
%e 3+1+1 _ | | | 3 1 1
%e 1+2+1+1 _|_ | | | 1 2 1 1
%e 2+1+1+1 _ | | | | 2 1 1 1
%e 1+1+1+1+1 | | | | | 1 1 1 1 1
%e .
%e Illustration of initial terms (n = 1..16):
%e .
%e . _ _
%e . _ _ _ _ _ _ _|_
%e . _ _ _ _ | _ | _ |
%e . | | | | | | | |
%e .
%e . 1 2 4 6 7 8
%e .
%e .
%e . _ _
%e . _ _ _
%e . _ _ _ _ _ _ _ _ _ _|_ _ _|_ _
%e . _ _ | _ | _ | _ |
%e . _|_ _|_ | _|_ | _|_ | _|_ |
%e . _ | _ | | _ | | _ | | _ | |
%e . | | | | | | | | | | | | | |
%e .
%e . 11 15 16 17 19
%e .
%e .
%e . _ _ _ _ _ _ _ _
%e . _ _ _ _ |
%e . _ _ _ _ _|_ _|_ _|_ |
%e . _ | _ | _ | _ | _ | |
%e . _|_|_ _|_|_ _|_|_ _|_|_ _|_|_ |
%e . _ | _ | _ | _ | _ | |
%e . _|_ | _|_ | _|_ | _|_ | _|_ | |
%e . _ | | _ | | _ | | _ | | _ | | |
%e . | | | | | | | | | | | | | | | |
%e .
%e . 21 22 23 27 35
%e .
%o (Python)
%o 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
%Y Cf. A001511, A005187, A006519, A006520, A011782, A139250, A187816, A187818, A206437, A225600, A228350, A228351, A228366, A228367, A228368, A228371, A228525, A228526.
%K nonn
%O 0,3
%A _Omar E. Pol_, Aug 21 2013
| 