A333217 -id:A333217 - cp's OEIS frontend

A107428 Number of gap-free compositions of n.

1, 2, 4, 6, 11, 21, 39, 71, 141, 276, 542, 1070, 2110, 4189, 8351, 16618, 33134, 66129, 131937, 263483, 526453, 1051984, 2102582, 4203177, 8403116, 16800894, 33593742, 67174863, 134328816, 268624026, 537192064, 1074288649, 2148414285, 4296543181, 8592585289

Offset: 1

N. J. A. Sloane, May 26 2005

nonn

A gap-free composition contains all the parts between its smallest and largest part. a(5)=11 because we have: 5, 3+2, 2+3, 2+2+1, 2+1+2, 1+2+2, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 1+1+1+1+1. - Geoffrey Critzer, Apr 13 2014

			From _Gus Wiseman_, Oct 04 2022: (Start)
The a(0) = 1 through a(5) = 11 gap-free compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (22)    (23)
                 (21)   (112)   (32)
                 (111)  (121)   (122)
                        (211)   (212)
                        (1111)  (221)
                                (1112)
                                (1121)
                                (1211)
                                (2111)
                                (11111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Alois P. Heinz, Plot of (a(n)-2^(n-2))/2^(n-2) for n = 42..1000
P. Hitczenko and A. Knopfmacher, Gap-free compositions and gap-free samples of geometric random variables, Discrete Math., 294 (2005), 225-239.

The unordered version (partitions) is A034296, ranked by A073491.
The initial case is A107429, unordered A000009, ranked by A333217.
The unordered complement is counted by A239955, ranked by A073492.
These compositions are ranked by A356841.
The complement is counted by A356846, ranked by A356842
A356230 ranks gapless factorization lengths, firsts A356603.
A356233 counts factorizations into gapless numbers.
Cf. A055932, A073493, A137921, A251729, A356224, A356843, A356845.

b:= proc(n, i, t) option remember; `if`(n=0, t!,
      `if`(i<1 or n add(b(n, i, 0), i=1..n):
seq(a(n), n=1..40);  # Alois P. Heinz, Apr 14 2014

Table[Length[Select[Level[Map[Permutations,IntegerPartitions[n]],{2}],Length[Union[#]]==Max[#]-Min[#]+1&]],{n,1,20}] (* Geoffrey Critzer, Apr 13 2014 *)
b[n_, i_, t_] := b[n, i, t] = If[n == 0, t!, If[i < 1 || n < i, 0, Sum[b[n - i*j, i - 1, t + j]/j!, {j, 1, n/i}]]]; a[n_] := Sum[b[n, i, 0], {i, 1, n}]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 30 2016, after Alois P. Heinz *)

a(n) ~ 2^(n-2). - Alois P. Heinz, Dec 07 2014

G.f.: Sum_{j>0} Sum_{k>=j} C({j..k},x) where C({s},x) = Sum_{i in {s}} (C({s}-{i},x)*x^i)/(1 - Sum_{i in {s}} (x^i)) is the g.f. for compositions such that the set of parts equals {s} with C({},x) = 1. - John Tyler Rascoe, Jun 01 2024

More terms from Vladeta Jovovic, May 26 2005

A246534 a(n) = Sum_{k=1..n} 2^(T(k)-1), where T(k)=k(k+1)/2 = A000217(k).

Original entry on oeis.org

0, 1, 5, 37, 549, 16933, 1065509, 135283237, 34495021605, 17626681066021, 18032025190548005, 36911520172609651237, 151152638972001256489509, 1238091191924352276155613733, 20283647694843594776223406899749, 664634281540152780046679753547072037

Offset: 0

M. F. Hasler, Aug 28 2014

nonn

Similar to A181388, this occurs as binary encoding of a straight n-omino lying on the y-axis, when the grid points of the first quadrant (N x N, N={0,1,2,...}) are given the weight 2^k, with k=0, 1,2, 3,4,5, ... filled in by antidiagonals.

Numbers k such that the k-th composition in standard order (row k of A066099) is a reversed initial interval. - Gus Wiseman, Apr 02 2020

			Label the cells of an infinite square matrix with 0,1,2,3,... along antidiagonals:
  0 1 3 6 10 ...
  2 4 7 ...
  5 8 ...
  9 ...
  ....
Now any subset of these cells can be represented by the sum of 2 raised to the power written in the given cells. In particular, the subset consisting of the first cell in the first 1, 2, 3, ... rows is represented by 2^0, 2^0+2^2, 2^0+2^2+2^5, ...

The version for prime (rather than binary) indices is A002110.
The non-strict generalization is A114994.
The non-reversed version is A164894.
Intersection of A333256 and A333217.
Partial sums of A036442.
Cf. A000120, A029931, A048793, A066099, A070939, A124766, A228351, A233564, A272919, A333218.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
Select[Range[0,1000],normQ[stc[#]]&&Greater@@stc[#]&] (* Gus Wiseman, Apr 02 2020 *)

t=0;vector(20,n,t+=2^(n*(n+1)/2-1)) \\ yields the vector starting with a[1]=1

t=0;vector(20,n,if(n>1,t+=2^(n*(n-1)/2-1))) \\ yields the vector starting with 0

a = 0
for n in range(1,17): print(a, end =', '); a += 1<<(n-1)*(n+2)//2 # Ya-Ping Lu, Jan 23 2024

A057335 a(0) = 1, and for n > 0, a(n) = A000040(A000120(n)) * a(floor(n/2)); essentially sequence A055932 generated using A000120, hence sorted by number of factors.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 18, 30, 16, 24, 36, 60, 54, 90, 150, 210, 32, 48, 72, 120, 108, 180, 300, 420, 162, 270, 450, 630, 750, 1050, 1470, 2310, 64, 96, 144, 240, 216, 360, 600, 840, 324, 540, 900, 1260, 1500, 2100, 2940, 4620, 486, 810, 1350, 1890, 2250, 3150, 4410

Offset: 0

Alford Arnold, Aug 27 2000

Note that for n>0 the prime divisors of a(n) are consecutive primes starting with 2. All of the least prime signatures (A025487) are included; with the other values forming A056808.
Using the formula, terms of b(n)= a(n)/A057334(n) are: 1, 1, 2, 2, 4, 4, 6, 6, 8, ..., indeed a(n) repeated. - Michel Marcus, Feb 09 2014
a(n) is the unique normal number whose unsorted prime signature is the k-th composition in standard order (graded reverse-lexicographic). This composition (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. A number is normal if its prime indices cover an initial interval of positive integers. Unsorted prime signature is the sequence of exponents in a number's prime factorization. - Gus Wiseman, Apr 19 2020

			From _Gus Wiseman_, Apr 19 2020: (Start)
The sequence of terms together with their prime indices begins:
      1: {}
      2: {1}
      4: {1,1}
      6: {1,2}
      8: {1,1,1}
     12: {1,1,2}
     18: {1,2,2}
     30: {1,2,3}
     16: {1,1,1,1}
     24: {1,1,1,2}
     36: {1,1,2,2}
     60: {1,1,2,3}
     54: {1,2,2,2}
     90: {1,2,2,3}
    150: {1,2,3,3}
    210: {1,2,3,4}
     32: {1,1,1,1,1}
     48: {1,1,1,1,2}
For example, the 27th composition in standard order is (1,2,1,1), and the normal number with prime signature (1,2,1,1) is 630 = 2*3*3*5*7, so a(27) = 630.
(End)

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Cf. A000120, A057334, A055932 and A056808.
Cf. A324939.
Unsorted prime signature is A124010.
Numbers whose prime signature is aperiodic are A329139.
The reversed version is A334031.
A partial inverse is A334032.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Aperiodic compositions are A328594.
- Normal compositions are A333217.
- Permutations are A333218.
- Heinz number is A333219.
Cf. A005867, A029931, A048793, A052409, A056239, A066099, A112798, A124767, A228351, A233249, A333220, A345974.
Related to A019565 via A122111 and to A000079 via A336321.

Table[Times @@ Map[If[# == 0, 1, Prime@ #] &, Accumulate@ IntegerDigits[n, 2]], {n, 0, 54}] (* Michael De Vlieger, May 23 2017 *)

mg(n) = if (n==0, 1, prime(hammingweight(n))); \\ A057334
lista(nn) = {my(v = vector(nn)); v[1] = 1; for (i=2, nn, v[i] = mg(i-1)*v[(i+1)\2];); v;} \\ Michel Marcus, Feb 09 2014

A057335(n) = if(0==n,1,prime(hammingweight(n))*A057335(n\2)); \\ Antti Karttunen, Jul 20 2020

a(n) = A057334(n) * a (repeated).
A334032(a(n)) = n; a(A334032(n)) = A071364(n). - Gus Wiseman, Apr 19 2020
a(n) = A122111(A019565(n)); A019565(n) = A122111(a(n)). - Peter Munn, Jul 18 2020
a(n) = A336321(2^n). - Peter Munn, Mar 04 2022
Sum_{n>=0} 1/a(n) = Sum_{n>=0} 1/A005867(n) = 2.648101... (A345974). - Amiram Eldar, Jun 26 2025

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003

New primary name from Antti Karttunen, Jul 20 2020

A333222 Numbers k such that every restriction of the k-th composition in standard order to a subinterval has a different sum.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 8, 9, 12, 16, 17, 18, 20, 24, 32, 33, 34, 40, 41, 48, 50, 64, 65, 66, 68, 69, 70, 72, 80, 81, 88, 96, 98, 104, 128, 129, 130, 132, 133, 134, 144, 145, 160, 161, 176, 192, 194, 196, 208, 256, 257, 258, 260, 261, 262, 264, 265, 268, 272, 274

Offset: 1

Gus Wiseman, Mar 17 2020

nonn

Also numbers whose binary indices together with 0 define a Golomb ruler.

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

			The list of terms together with the corresponding compositions begins:
    0: ()        41: (2,3,1)    130: (6,2)      262: (6,1,2)
    1: (1)       48: (1,5)      132: (5,3)      264: (5,4)
    2: (2)       50: (1,3,2)    133: (5,2,1)    265: (5,3,1)
    4: (3)       64: (7)        134: (5,1,2)    268: (5,1,3)
    5: (2,1)     65: (6,1)      144: (3,5)      272: (4,5)
    6: (1,2)     66: (5,2)      145: (3,4,1)    274: (4,3,2)
    8: (4)       68: (4,3)      160: (2,6)      276: (4,2,3)
    9: (3,1)     69: (4,2,1)    161: (2,5,1)    288: (3,6)
   12: (1,3)     70: (4,1,2)    176: (2,1,5)    289: (3,5,1)
   16: (5)       72: (3,4)      192: (1,7)      290: (3,4,2)
   17: (4,1)     80: (2,5)      194: (1,5,2)    296: (3,2,4)
   18: (3,2)     81: (2,4,1)    196: (1,4,3)    304: (3,1,5)
   20: (2,3)     88: (2,1,4)    208: (1,2,5)    320: (2,7)
   24: (1,4)     96: (1,6)      256: (9)        321: (2,6,1)
   32: (6)       98: (1,4,2)    257: (8,1)      324: (2,4,3)
   33: (5,1)    104: (1,2,4)    258: (7,2)      328: (2,3,4)
   34: (4,2)    128: (8)        260: (6,3)      352: (2,1,6)
   40: (2,4)    129: (7,1)      261: (6,2,1)    384: (1,8)

Wikipedia, Golomb ruler

A subset of A233564.
Also a subset of A333223.
These compositions are counted by A169942 and A325677.
The number of distinct nonzero subsequence-sums is A333224.
The number of distinct subsequence-sums is A333257.
Lengths of optimal Golomb rulers are A003022.
Inequivalent optimal Golomb rulers are counted by A036501.
Complete rulers are A103295, with perfect case A103300.
Knapsack partitions are counted by A108917, with strict case A275972.
Distinct subsequences are counted by A124770 and A124771.
Golomb subsets are counted by A143823.
Heinz numbers of knapsack partitions are A299702.
Knapsack compositions are counted by A325676.
Maximal Golomb rulers are counted by A325683.
Cf. A000120, A029931, A048793, A066099, A070939, A228351, A295235, A325678, A325680, A325768, A325779, A333217.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,300],UnsameQ@@ReplaceList[stc[#],{_,s__,_}:>Plus[s]]&]

A022340 Even Fibbinary numbers (A003714); also 2*Fibbinary(n).

Original entry on oeis.org

0, 2, 4, 8, 10, 16, 18, 20, 32, 34, 36, 40, 42, 64, 66, 68, 72, 74, 80, 82, 84, 128, 130, 132, 136, 138, 144, 146, 148, 160, 162, 164, 168, 170, 256, 258, 260, 264, 266, 272, 274, 276, 288, 290, 292, 296, 298, 320, 322, 324, 328, 330, 336, 338, 340, 512

Offset: 0

Marc LeBrun

nonn

Positions of ones in binomial(3k+2,k+1)/(3k+2) modulo 2 (A085405). - Paul D. Hanna, Jun 29 2003
Construction: start with strings S(0)={0}, S(1)={2}; for k>=2, concatenate all prior strings excluding S(k-1) and add 2^k to each element in the resulting string to obtain S(k); this sequence is the concatenation of all such generated strings: {S(0),S(1),S(2),...}. Example: for k=5, concatenate {S(0),S(1),S(2),S(3)} = {0, 2, 4, 8,10}; add 2^5 to each element to obtain S(5)={32,34,38,40,42}. - Paul D. Hanna, Jun 29 2003
From Gus Wiseman, Apr 08 2020: (Start)
The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence lists all numbers k such that the k-th composition in standard order has no ones. For example, the sequence together with the corresponding compositions begins:
()          80: (2,5)        260: (6,3)
(2)         82: (2,3,2)      264: (5,4)
(3)         84: (2,2,3)      266: (5,2,2)
(4)        128: (8)          272: (4,5)
(2,2)      130: (6,2)        274: (4,3,2)
(5)        132: (5,3)        276: (4,2,3)
(3,2)      136: (4,4)        288: (3,6)
(2,3)      138: (4,2,2)      290: (3,4,2)
(6)        144: (3,5)        292: (3,3,3)
(4,2)      146: (3,3,2)      296: (3,2,4)
(3,3)      148: (3,2,3)      298: (3,2,2,2)
(2,4)      160: (2,6)        320: (2,7)
(2,2,2)    162: (2,4,2)      322: (2,5,2)
(7)        164: (2,3,3)      324: (2,4,3)
(5,2)      168: (2,2,4)      328: (2,3,4)
(4,3)      170: (2,2,2,2)    330: (2,3,2,2)
(3,4)      256: (9)          336: (2,2,5)
(3,2,2)    258: (7,2)        338: (2,2,3,2)
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Equals 2 * A003714.
Cf. A006013, A001045, A085405, A085407.
Compositions with no ones are counted by A212804.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Compositions without terms > 2 are A003754.
- Compositions without ones are A022340 (this sequence).
- Sum is A070939.
- Compositions with no twos are A175054.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Runs-resistance is A333628.
Cf. A066099, A124767, A228351, A318928, A333218.

a022340 = (* 2) . a003714 -- Reinhard Zumkeller, Feb 03 2015

f[n_Integer] := Block[{k = Ceiling[ Log[ GoldenRatio, n*Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; FromDigits[fr, 2]]; Select[f /@ Range[0, 95], EvenQ[ # ] &] (* Robert G. Wilson v, Sep 18 2004 *)
Select[Range[2, 512, 2], BitAnd[#, 2#] == 0 &] (* Alonso del Arte, Jun 18 2012 *)

from itertools import count, islice
def A022340_gen(startvalue=0): # generator of terms >= startvalue
    return filter(lambda n:not n&(n>>1),count(max(0,startvalue+(startvalue&1)),2))
A022340_list = list(islice(A022340_gen(),30)) # Chai Wah Wu, Sep 07 2022

def A022340(n):
    tlist, s = [1,2], 0
    while tlist[-1]+tlist[-2] <= n: tlist.append(tlist[-1]+tlist[-2])
    for d in tlist[::-1]:
        if d <= n:
            s += 1
            n -= d
        s <<= 1
    return s # Chai Wah Wu, Apr 24 2025

For n>0, a(F(n))=2^n, a(F(n)-1)=A001045(n+2)-1, where F(n) is the n-th Fibonacci number with F(0)=F(1)=1.

a(n) + a(n)/2 = a(n) XOR a(n)/2, see A106409. - Reinhard Zumkeller, May 02 2005

Edited by Ralf Stephan, Sep 01 2004

A335460 Number of (1,2,1) or (2,1,2)-matching permutations of the prime indices of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 1, 1, 0, 0, 3, 0, 1, 0, 1, 0, 2, 0, 2, 0, 0, 0, 6, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 8, 0, 0, 1, 1, 0, 0, 0, 3, 0, 0, 0, 6, 0, 0, 0

Offset: 1

Gus Wiseman, Jun 20 2020

nonn

Depends only on sorted prime signature (A118914).
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(n) compositions for n = 12, 24, 48, 36, 60, 72:
  (121)  (1121)  (11121)  (1212)  (1213)  (11212)
         (1211)  (11211)  (1221)  (1231)  (11221)
                 (12111)  (2112)  (1312)  (12112)
                          (2121)  (1321)  (12121)
                                  (2131)  (12211)
                                  (3121)  (21112)
                                          (21121)
                                          (21211)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Positions of zeros are A303554.
The (1,2,1)-matching part is A335446.
The (2,1,2)-matching part is A335453.
Replacing "or" with "and" gives A335462.
Permutations of prime indices are counted by A008480.
Unsorted prime signature is A124010. Sorted prime signature is A118914.
STC-numbers of permutations of prime indices are A333221.
(1,2,1) and (2,1,2)-avoiding permutations of prime indices are A333175.
Patterns matched by standard compositions are counted by A335454.
(1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.
Dimensions of downsets of standard compositions are A335465.
Cf. A056239, A056986, A112798, A158005, A181796, A335451, A335452, A335463.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Permutations[primeMS[n]],MatchQ[#,{_,x_,_,y_,_,x_,_}/;x!=y]&]],{n,100}]

A335515 Number of patterns of length n matching the pattern (1,2,3).

Original entry on oeis.org

0, 0, 0, 1, 19, 257, 3167, 38909, 498235, 6811453, 100623211, 1612937661, 28033056683, 526501880989, 10639153638795, 230269650097469, 5315570416909995, 130370239796988957, 3385531348514480651, 92801566389186549245, 2677687663571344712043, 81124824154544921317597

Offset: 0

Gus Wiseman, Jun 19 2020

nonn

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(3) = 1 through a(4) = 19 patterns:
  (1,2,3)  (1,1,2,3)
           (1,2,1,3)
           (1,2,2,3)
           (1,2,3,1)
           (1,2,3,2)
           (1,2,3,3)
           (1,2,3,4)
           (1,2,4,3)
           (1,3,2,3)
           (1,3,2,4)
           (1,3,4,2)
           (1,4,2,3)
           (2,1,2,3)
           (2,1,3,4)
           (2,3,1,4)
           (2,3,4,1)
           (3,1,2,3)
           (3,1,2,4)
           (4,1,2,3)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The complement A226316 is the avoiding version.
Compositions matching this pattern are counted by A335514 and ranked by A335479.
Permutations of prime indices matching this pattern are counted by A335520.
Patterns are counted by A000670 and ranked by A333217.
Patterns matching the pattern (1,1) are counted by A019472.
Permutations matching (1,2,3) are counted by A056986.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A158005, A158009, A238279, A333218, A333379, A333942.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{_,x_,_,y_,_,z_,_}/;x

seq(n)=Vec( serlaplace(1/(2-exp(x + O(x*x^n)))) - 1/2 - 1/(1+sqrt(1-8*x+8*x^2 + O(x*x^n))), -(n+1)) \\ Andrew Howroyd, Jan 28 2024

a(n) = A000670(n) - A226316(n). - Andrew Howroyd, Jan 28 2024

a(9) onwards from Andrew Howroyd, Jan 28 2024

A335514 Number of (1,2,3)-matching compositions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 4, 14, 42, 114, 292, 714, 1686, 3871, 8696, 19178, 41667, 89386, 189739, 399144, 833290, 1728374, 3565148, 7319212, 14965880, 30496302, 61961380, 125577752, 253971555, 512716564, 1033496947, 2080572090, 4183940550, 8406047907, 16875834728

Offset: 0

Gus Wiseman, Jun 22 2020

nonn

			The a(6) = 1 through a(8) = 14 compositions:
  (1,2,3)  (1,2,4)    (1,2,5)
           (1,1,2,3)  (1,3,4)
           (1,2,1,3)  (1,1,2,4)
           (1,2,3,1)  (1,2,1,4)
                      (1,2,2,3)
                      (1,2,3,2)
                      (1,2,4,1)
                      (2,1,2,3)
                      (1,1,1,2,3)
                      (1,1,2,1,3)
                      (1,1,2,3,1)
                      (1,2,1,1,3)
                      (1,2,1,3,1)
                      (1,2,3,1,1)

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for permutations is A056986.
The avoiding version is A102726.
These compositions are ranked by A335479.
The version for patterns is A335515.
The version for prime indices is A335520.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Patterns matched by compositions are counted by A335456.
Cf. A011782, A032020, A106356, A226316, A269134, A333755, A335465, A335521.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,_,y_,_,z_,_}/;x

a(n > 0) = 2^(n - 1) - A102726(n).

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A087117 Number of zeros in the longest string of consecutive zeros in the binary representation of n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 1, 0, 3, 2, 1, 1, 2, 1, 1, 0, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 3, 3, 2, 2

Offset: 0

Reinhard Zumkeller, Aug 14 2003

The following four statements are equivalent: a(n) = 0; n = 2^k - 1 for some k > 0; A087116(n) = 0; A023416(n) = 0.

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. Then a(k) is the maximum part of this composition, minus one. The maximum part is A333766(k). - Gus Wiseman, Apr 09 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A023416, A007088, A007814.
Cf. A025480, A038374, A090046, A090047, A090048, A090049, A090050.
Positions of zeros are A000225.
Positions of terms <= 1 are A003754.
Positions of terms > 0 are A062289.
Positions of first appearances are A131577.
The version for prime indices is A252735.
The proper maximum is A333766.
The version for minimum is A333767.
Maximum prime index is A061395.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Runs are counted by A124767.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Runs-resistance is A333628.
- Weakly decreasing compositions are A114994.
- Weakly increasing compositions are A225620.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
Cf. A029931, A048793, A061395, A087117, A228351, A328594, A333217, A333218, A333219, A333767, A333768.

import Data.List (unfoldr, group)
a087117 0       = 1
a087117 n
  | null $ zs n = 0
  | otherwise   = maximum $ map length $ zs n where
  zs = filter ((== 0) . head) . group .
       unfoldr (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, May 01 2012

A087117 := proc(n)
    local d,l,zlen ;
    if n = 0 then
        return 1 ;
    end if;
    d := convert(n,base,2) ;
    for l from nops(d)-1 to 0 by -1 do
        zlen := [seq(0,i=1..l)] ;
        if verify(zlen,d,'sublist') then
            return l ;
        end if;
    end do:
    return 0 ;
end proc; # R. J. Mathar, Nov 05 2012

nz[n_]:=Max[Length/@Select[Split[IntegerDigits[n,2]],MemberQ[#,0]&]]; Array[nz,110,0]/.-\[Infinity]->0 (* Harvey P. Dale, Sep 05 2017 *)

h(n)=if(n<2, return(0)); my(k=valuation(n,2)); if(k, max(h(n>>k), k), n++; n>>=valuation(n,2); h(n-1))
a(n)=if(n,h(n),1) \\ Charles R Greathouse IV, Apr 06 2022

a(n) = max(A007814(n), a(A025480(n-1))) for n >= 2. - Robert Israel, Feb 19 2017
a(2n+1) = a(n) (n>=1); indeed, the binary form of 2n+1 consists of the binary form of n with an additional 1 at the end - Emeric Deutsch, Aug 18 2017
For n > 0, a(n) = A333766(n) - 1. - Gus Wiseman, Apr 09 2020

A335462 Number of (1,2,1) and (2,1,2)-matching permutations of the prime indices of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Jun 20 2020

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(n) permutations for n = 36, 72, 270, 144, 300:
  (1,2,1,2)  (1,1,2,1,2)  (2,1,2,3,2)  (1,1,1,2,1,2)  (1,2,3,1,3)
  (2,1,2,1)  (1,2,1,1,2)  (2,1,3,2,2)  (1,1,2,1,1,2)  (1,3,1,2,3)
             (1,2,1,2,1)  (2,2,1,3,2)  (1,1,2,1,2,1)  (1,3,1,3,2)
             (2,1,1,2,1)  (2,2,3,1,2)  (1,2,1,1,1,2)  (1,3,2,1,3)
             (2,1,2,1,1)  (2,3,1,2,2)  (1,2,1,1,2,1)  (1,3,2,3,1)
                          (2,3,2,1,2)  (1,2,1,2,1,1)  (2,1,3,1,3)
                                       (2,1,1,1,2,1)  (2,3,1,3,1)
                                       (2,1,1,2,1,1)  (3,1,2,1,3)
                                       (2,1,2,1,1,1)  (3,1,2,3,1)
                                                      (3,1,3,1,2)
                                                      (3,1,3,2,1)
                                                      (3,2,1,3,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The avoiding version is A333175.
Replacing "and" with "or" gives A335460.
Positions of nonzero terms are A335463.
Permutations of prime indices are counted by A008480.
Unsorted prime signature is A124010. Sorted prime signature is A118914.
STC-numbers of permutations of prime indices are A333221.
Patterns matched by standard compositions are counted by A335454.
Dimensions of downsets of standard compositions are A335465.
Cf. A056239, A056986, A112798, A158005, A181796, A335451, A335452.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Permutations[primeMS[n]],MatchQ[#,{_,x_,_,y_,_,x_,_}/;x_,x_,_,y_,_,x_,_}/;x>y]&]],{n,100}]

cp's OEIS Frontend

A107428 Number of gap-free compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A246534 a(n) = Sum_{k=1..n} 2^(T(k)-1), where T(k)=k(k+1)/2 = A000217(k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A057335 a(0) = 1, and for n > 0, a(n) = A000040(A000120(n)) * a(floor(n/2)); essentially sequence A055932 generated using A000120, hence sorted by number of factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A333222 Numbers k such that every restriction of the k-th composition in standard order to a subinterval has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A022340 Even Fibbinary numbers (A003714); also 2*Fibbinary(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Python

Formula

Extensions

A335460 Number of (1,2,1) or (2,1,2)-matching permutations of the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335515 Number of patterns of length n matching the pattern (1,2,3).

Views

Author

Keywords

Comments

Examples