A178472 -id:A178472 - cp's OEIS frontend

A337697 Number of pairwise coprime compositions of n with no 1's, where a singleton is not considered coprime.

0, 0, 0, 0, 0, 2, 0, 4, 2, 4, 8, 8, 14, 10, 16, 12, 30, 38, 46, 46, 48, 52, 62, 152, 96, 156, 112, 190, 256, 338, 420, 394, 326, 402, 734, 622, 1150, 802, 946, 898, 1730, 1946, 2524, 2200, 2328, 2308, 3356, 5816, 4772, 5350, 4890, 6282, 6316, 12092, 8902

Offset: 0

Gus Wiseman, Oct 06 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. These compositions must be strict.

			The a(5) = 2 through a(12) = 14 compositions (empty column indicated by dot):
  (2,3)  .  (2,5)  (3,5)  (2,7)  (3,7)    (2,9)  (5,7)
  (3,2)     (3,4)  (5,3)  (4,5)  (7,3)    (3,8)  (7,5)
            (4,3)         (5,4)  (2,3,5)  (4,7)  (2,3,7)
            (5,2)         (7,2)  (2,5,3)  (5,6)  (2,7,3)
                                 (3,2,5)  (6,5)  (3,2,7)
                                 (3,5,2)  (7,4)  (3,4,5)
                                 (5,2,3)  (8,3)  (3,5,4)
                                 (5,3,2)  (9,2)  (3,7,2)
                                                 (4,3,5)
                                                 (4,5,3)
                                                 (5,3,4)
                                                 (5,4,3)
                                                 (7,2,3)
                                                 (7,3,2)

A022340 intersected with A333227 is a ranking sequence (using standard compositions A066099) for these compositions.
A212804 does not require coprimality, with unordered version A002865.
A337450 is the relatively prime instead of pairwise coprime version, with strict case A337451 and unordered version A302698.
A337462 allows 1's, with strict case A337561 (or A101268 with singletons), unordered version A327516 with Heinz numbers A302696, and 3-part case A337461.
A337485 is the unordered version (or A007359 with singletons considered coprime), with Heinz numbers A337984.
A337563 is the case of unordered triples.
Cf. A078374, A178472, A302568, A302697, A305713, A307719, A332004, A337562.

Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],!MemberQ[#,1]&&CoprimeQ@@#&]],{n,0,30}]

For n > 1, the version where singletons are considered coprime is a(n) + 1.

A329132 Numbers whose augmented differences of prime indices are a periodic sequence.

Original entry on oeis.org

4, 8, 15, 16, 32, 55, 64, 90, 105, 119, 128, 225, 253, 256, 403, 512, 540, 550, 697, 893, 935, 1024, 1155, 1350, 1357, 1666, 1943, 2048, 2263, 3025, 3071, 3150, 3240, 3375, 3451, 3927, 3977, 4096, 4429, 5123, 5500, 5566, 6731, 7735, 8083, 8100, 8192, 9089

Offset: 1

Gus Wiseman, Nov 06 2019

nonn

The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).
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.
A sequence is periodic if its cyclic rotations are not all different.

			The sequence of terms together with their augmented differences of prime indices begins:
     4: (1,1)
     8: (1,1,1)
    15: (2,2)
    16: (1,1,1,1)
    32: (1,1,1,1,1)
    55: (3,3)
    64: (1,1,1,1,1,1)
    90: (2,1,2,1)
   105: (2,2,2)
   119: (4,4)
   128: (1,1,1,1,1,1,1)
   225: (1,2,1,2)
   253: (5,5)
   256: (1,1,1,1,1,1,1,1)
   403: (6,6)
   512: (1,1,1,1,1,1,1,1,1)
   540: (2,1,1,2,1,1)
   550: (3,1,3,1)
   697: (7,7)
   893: (8,8)

Complement of A329133.
These are the Heinz numbers of the partitions counted by A329143.
Periodic binary words are A152061.
Periodic compositions are A178472.
Numbers whose binary expansion is periodic are A121016.
Numbers whose prime signature is periodic are A329140.
Numbers whose differences of prime indices are periodic are A329134.
Cf. A000961, A027375, A056239, A112798, A325356, A325389, A325394, A328594, A329135, A329136, A329139.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
aug[y_]:=Table[If[i

A304250 Perfect powers whose prime factors span an initial interval of prime numbers.

Original entry on oeis.org

4, 8, 16, 32, 36, 64, 128, 144, 216, 256, 324, 512, 576, 900, 1024, 1296, 1728, 2048, 2304, 2916, 3600, 4096, 5184, 5832, 7776, 8100, 8192, 9216, 11664, 13824, 14400, 16384, 20736, 22500, 26244, 27000, 32400, 32768, 36864, 44100, 46656, 57600, 65536, 72900

Offset: 1

Gus Wiseman, May 13 2018

nonn

The multiset of prime indices of a(n) is the a(n)-th row of A112798. This multiset is normal, meaning it spans an initial interval of positive integers, and periodic, meaning its multiplicities have a common divisor greater than 1.

			Sequence of all normal periodic multisets begins
4:    {1,1}
8:    {1,1,1}
16:   {1,1,1,1}
32:   {1,1,1,1,1}
36:   {1,1,2,2}
64:   {1,1,1,1,1,1}
128:  {1,1,1,1,1,1,1}
144:  {1,1,1,1,2,2}
216:  {1,1,1,2,2,2}
256:  {1,1,1,1,1,1,1,1}
324:  {1,1,2,2,2,2}
512:  {1,1,1,1,1,1,1,1,1}
576:  {1,1,1,1,1,1,2,2}
900:  {1,1,2,2,3,3}
1024: {1,1,1,1,1,1,1,1,1,1}

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

Cf. A000837, A000961 A001597, A007916, A018783, A052409, A052410, A055932, A056239, A112798, A178472, A303431, A303709, A304450, A368682.

Select[Range[1000],FactorInteger[#][[-1,1]]==Prime[Length[FactorInteger[#]]]&&GCD@@FactorInteger[#][[All,2]]>1&]

Intersection of A001597 and A055932.

A329141 Number of Lyndon compositions of n that are not weakly increasing.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 4, 11, 28, 60, 131, 263, 530, 1029, 2009, 3853, 7414, 14152, 27105, 51755, 99069, 189558, 363468, 697302, 1340220, 2578362, 4968001, 9582682, 18508226, 35784670, 69266825, 134207336, 260290846, 505274108, 981691926

Offset: 1

Gus Wiseman, Nov 10 2019

nonn

A Lyndon composition of n is a finite sequence of positive integers summing to n that is lexicographically strictly less than all of its cyclic rotations.

			The a(6) = 1 through a(8) = 11 compositions:
  (132)  (142)    (143)
         (1132)   (152)
         (1213)   (1142)
         (11212)  (1214)
                  (1232)
                  (1322)
                  (11132)
                  (11213)
                  (11312)
                  (12122)
                  (111212)

Lyndon compositions are A059966.
Lyndon compositions that are weakly increasing are A167934.
Binary Lyndon words are A001037.
Necklace compositions are A008965.
Cf. A000031, A000740, A178472, A318731, A328596, A329131, A329145.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!OrderedQ[#]&&neckQ[#]&&aperQ[#]&]],{n,10}]

a(n) = A059966(n) - A167934(n).

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 2, 3, 0, 0, 2, 4, 6, 4, 0, 0, 4, 6, 9, 8, 5, 0, 0, 2, 6, 15, 20, 15, 6, 0, 0, 4, 8, 24, 32, 35, 18, 7, 0, 0, 3, 10, 27, 56, 70, 54, 28, 8, 0, 0, 4, 12, 42, 84, 125, 120, 84, 32, 9, 0, 0, 2, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset: 0

Gus Wiseman, Apr 16 2020

A composition of n is a finite sequence of positive integers summing to n.

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   2   3   0
   0   2   4   6   4   0
   0   4   6   9   8   5   0
   0   2   6  15  20  15   6   0
   0   4   8  24  32  35  18   7   0
   0   3  10  27  56  70  54  28   8   0
   0   4  12  42  84 125 120  84  32   9   0
   0   2  10  45 120 210 252 210 120  45  10   0
   0   6  18  66 168 335 450 462 320 162  50  11   0
Row n = 6 counts the following compositions (empty columns indicated by dots):
  .  (6)       (15)    (114)  (1113)  (11112)  .
     (33)      (24)    (123)  (1122)  (11121)
     (222)     (42)    (132)  (1131)  (11211)
     (111111)  (51)    (141)  (1221)  (12111)
               (1212)  (213)  (1311)  (21111)
               (2121)  (231)  (2112)
                       (312)  (2211)
                       (321)  (3111)
                       (411)

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Column k = 1 is A000005.
Row sums are A011782.
Diagonal T(2n,n) is A045630(n).
The strict version is A072574.
A version counting runs is A238279.
Column k = n - 1 is A254667.
Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Period of binary expansion is A302291.
Numbers whose prime signature is aperiodic are A329139.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Rotational symmetries are counted by A138904.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A291166, A328595, A328596, A329312, A329313, A329326.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Function[c,Length[Union[Array[RotateRight[c,#]&,Length[c]]]]==k]]],{n,0,10},{k,0,n}]

T(n,k)=if(n==0, k==0, sumdiv(n, m, sumdiv(gcd(k,m), d, moebius(d)*binomial(m/d-1, k/d-1)))) \\ Andrew Howroyd, Jan 19 2023

T(n,k) = Sum_{m|n} Sum_{d|gcd(k,m)} mu(d)*binomial(m/d-1, k/d-1) for n > 0. - Andrew Howroyd, Jan 19 2023

A298971 Number of compositions of n that are proper powers of Lyndon words.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 1, 69, 1, 110, 21, 188, 1, 381, 7, 632, 59, 1184, 1, 2300, 1, 4115, 189, 7712, 25, 14939, 1, 27596, 633, 52517, 1, 101050, 1, 190748, 2247, 364724, 1, 703331, 19, 1342283, 7713, 2581430, 1, 4985609, 193

Offset: 1

Gus Wiseman, Jan 30 2018

nonn

a(n) is the number of compositions of n that are not Lyndon words but are of the form p * p * ... * p where * is concatenation and p is a Lyndon word.

			The a(12) = 16 compositions: 111111111111, 1111211112, 11131113, 112112112, 11221122, 114114, 12121212, 123123, 131313, 132132, 1515, 222222, 2424, 3333, 444, 66.

Cf. A000005, A000031, A000740, A000961, A001045, A008965, A019536, A034691, A051953, A052823, A059966, A060223, A178472, A185700, A296302, A296373.

Table[Sum[DivisorSum[d,MoebiusMu[d/#]*(2^#-1)&]/d,{d,Most@Divisors[n]}],{n,100}]

a(n) = sumdiv(n, d, (2^d-1)*(eulerphi(n/d)-moebius(n/d))/n); \\ Michel Marcus, Jan 31 2018

a(n) = Sum_{d|n} (2^d-1)*(phi(n/d)-mu(n/d))/n.

a(n) = A008965(n) - A059966(n).

A303974 Regular triangle where T(n,k) is the number of aperiodic multisets of size k that fit within some normal multiset of size n.

Original entry on oeis.org

1, 2, 1, 3, 3, 3, 4, 6, 10, 6, 5, 10, 22, 23, 15, 6, 15, 40, 57, 62, 27, 7, 21, 65, 115, 165, 129, 63, 8, 28, 98, 205, 356, 385, 318, 120, 9, 36, 140, 336, 676, 914, 1005, 676, 252, 10, 45, 192, 518, 1176, 1885, 2524, 2334, 1524, 495, 11, 55, 255, 762, 1918, 3528, 5495, 6319, 5607, 3261, 1023

Offset: 1

Gus Wiseman, May 03 2018

A multiset is normal if it spans an initial interval of positive integers. It is aperiodic if its multiplicities are relatively prime.

			Triangle begins:
1
2    1
3    3    3
4    6   10    6
5   10   22   23   15
6   15   40   57   62   27
7   21   65  115  165  129   63
8   28   98  205  356  385  318  120
9   36  140  336  676  914 1005  676  252
The a(4,3) = 10 multisets: (112), (113), (122), (123), (124), (133), (134), (223), (233), (234).
The a(5,4) = 23 multisets:
(1112), (1222),
(1113), (1123), (1223), (1233), (1333), (2223), (2333),
(1124), (1134), (1224), (1234), (1244), (1334), (1344), (2234), (2334), (2344),
(1235), (1245), (1345), (2345).

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Row sums are A303976.

Cf. A000740, A000837, A001597, A007716, A007916, A027941, A178472, A210554, A301700, A303431, A303546, A303551, A303945.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length/@GatherBy[Select[Union@@Rest/@Subsets/@allnorm[n],GCD@@Length/@Split[#]===1&],Length],{n,10}]

T(n,k)={sumdiv(k, d, moebius(k/d)*sum(i=1, d, binomial(d-1, i-1)*binomial(n-k+i, i)))} \\ Andrew Howroyd, Sep 18 2018

T(n,k) = Sum_{d|k} mu(k/d) * Sum_{i=1..d} binomial(d-1, i-1)*binomial(n-k+i, i). - Andrew Howroyd, Sep 18 2018

Terms a(56) and beyond from Andrew Howroyd, Sep 18 2018

A331888 Number of compositions (ordered partitions) of n into parts having a common factor > 1 with n.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 1, 8, 4, 17, 1, 60, 1, 65, 19, 128, 1, 800, 1, 683, 67, 1025, 1, 11005, 16, 4097, 256, 9203, 1, 369426, 1, 32768, 1027, 65537, 79, 2124475, 1, 262145, 4099, 1424118, 1, 48987720, 1, 2127107, 96334, 4194305, 1, 411836297, 64, 67919981, 65539

Offset: 0

Ilya Gutkovskiy, Jan 30 2020

nonn

			a(9) = 4 because we have [9], [6, 3], [3, 6] and [3, 3, 3].

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for sequences related to compositions

Cf. A182986 (positions of 1's), A100347, A121998, A178472, A331885, A331887.

a:= proc(m) option remember; local b; b:=
      proc(n) option remember; `if`(n=0, 1,
        add(`if`(igcd(j, m)>1, b(n-j), 0), j=1..n))
      end; forget(b); b(m$2)
    end:
seq(a(n), n=0..82);  # Alois P. Heinz, Jan 30 2020

Table[SeriesCoefficient[1/(1 - Sum[Boole[GCD[k, n] > 1] x^k, {k, 1, n}]), {x, 0, n}], {n, 0, 51}]

a(n) = [x^n] 1 / (1 - Sum_{k: gcd(n,k) > 1} x^k).

A303976 Number of different aperiodic multisets that fit within some normal multiset of size n.

Original entry on oeis.org

1, 3, 9, 26, 75, 207, 565, 1518, 4044, 10703, 28234, 74277, 195103, 511902, 1342147, 3517239, 9214412, 24134528, 63204417, 165505811, 433361425, 1134664831, 2970787794, 7777975396, 20363634815, 53313819160, 139579420528, 365427311171, 956707667616, 2504704955181

Offset: 1

Gus Wiseman, May 03 2018

nonn

A multiset is normal if it spans an initial interval of positive integers. It is aperiodic if its multiplicities are relatively prime.

			The a(4) = 26 aperiodic multisets:
(1), (2), (3), (4),
(12), (13), (14), (23), (24), (34),
(112), (113), (122), (123), (124), (133), (134), (223), (233), (234),
(1112), (1123), (1222), (1223), (1233), (1234).

Andrew Howroyd, Table of n, a(n) for n = 1..500

Row sums of A303974.

Cf. A000740, A000837, A007916, A027941, A178472, A210554, A301700, A303431, A303546, A303551, A303945.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Select[Union@@Rest/@Subsets/@allnorm[n],GCD@@Length/@Split[#]===1&]],{n,10}]

seq(n)={Vec(sum(d=1, n, moebius(d)*x^d/(1 - x - x^d*(2-x)) + O(x*x^n))/(1-x))} \\ Andrew Howroyd, Feb 04 2021

a(n) = Sum_{k=1..n} Sum_{d|k} mu(k/d) * Sum_{i=1..d} binomial(d-1, i-1)*binomial(n-k+i, i). - Andrew Howroyd, Sep 18 2018

G.f.: Sum_{d>=1} mu(d)*x^d/((1 - x - x^d*(2-x))*(1-x)). - Andrew Howroyd, Feb 04 2021

Terms a(13) and beyond from Andrew Howroyd, Sep 18 2018

A329143 Number of integer partitions of n whose augmented differences are a periodic word.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 1, 1, 3, 2, 2, 3, 2, 2, 4, 4, 5, 3, 5, 2, 10, 5, 6, 5, 10, 5, 11, 7, 13, 6, 15, 6, 20, 11, 18, 12, 27, 8, 27, 16, 32, 14, 35, 14, 42, 23, 43, 17, 56, 17, 61, 31, 67, 25, 78, 28, 88, 41, 89, 35, 119, 39, 116, 60, 131, 52, 154, 52, 170, 75, 182

Offset: 0

Gus Wiseman, Nov 10 2019

nonn

The augmented differences aug(y) of an integer partition y of length k are given by aug(y)i = y_i - y{i + 1} + 1 if i < k and aug(y)_k = y_k. For example, aug(6,5,5,3,3,3) = (2,1,3,1,1,3).

A finite sequence is periodic if its cyclic rotations are not all different.

			The a(n) partitions for n = 2, 5, 8, 14, 16, 22:
  11  32     53        95              5533              7744
      11111  3221      5432            7441              9652
             11111111  32222111        533311            554332
                       11111111111111  33222211          54333211
                                       1111111111111111  332222221111
                                                         1111111111111111111111

The Heinz numbers of these partitions are given by A329132.
The aperiodic version is A329136.
The non-augmented version is A329144.
Periodic binary words are A152061.
Periodic compositions are A178472.
Numbers whose binary expansion is periodic are A121016.
Numbers whose prime signature is periodic are A329140.
Cf. A000740, A027375, A328594, A329133, A329135, A325351, A325356, A329134.

aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
aug[y_]:=Table[If[i

a(n) + A329136(n) = A000041(n).

More terms from Jinyuan Wang, Jun 27 2020

cp's OEIS Frontend

A337697 Number of pairwise coprime compositions of n with no 1's, where a singleton is not considered coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A329132 Numbers whose augmented differences of prime indices are a periodic sequence.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A304250 Perfect powers whose prime factors span an initial interval of prime numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A329141 Number of Lyndon compositions of n that are not weakly increasing.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A298971 Number of compositions of n that are proper powers of Lyndon words.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A303974 Regular triangle where T(n,k) is the number of aperiodic multisets of size k that fit within some normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A331888 Number of compositions (ordered partitions) of n into parts having a common factor > 1 with n.

Views

Author