A178472 -id:A178472 - cp's OEIS frontend

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

0, 0, 1, 1, 1, 3, 1, 2, 5, 3, 2, 8, 2, 5, 9, 7, 5, 12, 7, 7, 19, 9, 9, 21, 12, 15, 23, 18, 17, 29, 21, 19, 42, 23, 31, 42, 38, 29, 53, 43, 44, 62, 49, 52, 79, 55, 72, 75, 87, 63, 117, 79, 104, 107, 120, 99, 156, 117, 143, 147

Offset: 1

Gus Wiseman, Nov 10 2019

nonn

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

			The a(n) partitions for n = 3, 6, 8, 9, 12, 15, 16:
  111  222     2222      333        444           555              4444
       321     11111111  432        543           654              7531
       111111            531        642           753              44332
                         32211      741           852              3332221
                         111111111  3333          951              4332211
                                    222222        33333            22222222
                                    3222111       54321            1111111111111111
                                    111111111111  322221111
                                                  111111111111111

The Heinz numbers of these partitions are given by A329134.
The augmented version is 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.
Cf. A000740, A027375, A059966, A328594, A328596, A329132, A329135, A329136.

aperQ[q_]:=Array[RotateRight[q,#1]&,Length[q],1,UnsameQ];
Table[Length[Select[IntegerPartitions[n],!aperQ[Differences[#]]&]],{n,30}]

A109511 Number of subsets of the first n numbers having a common divisor greater than 1.

Original entry on oeis.org

0, 1, 2, 4, 5, 10, 11, 19, 23, 40, 41, 79, 80, 145, 164, 292, 293, 577, 578, 1096, 1163, 2188, 2189, 4357, 4373, 8470, 8726, 16924, 16925, 33832, 33833, 66601, 67628, 133165, 133244, 266332, 266333, 528478, 532577, 1056985, 1056986, 2113717

Offset: 1

Reinhard Zumkeller, Jul 01 2005

nonn

			a(6) = #{{2}, {3}, {4}, {5}, {6}, {2,4}, {2,6}, {3,6}, {4,6}, {2,4,6}} = 10.

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Eric Weisstein's World of Mathematics, Inclusion-Exclusion Principle.

Partial sums of A178472.

Cf. A008683, A000225, A085945.

Table[Sum[-MoebiusMu[k] (2^Floor[n/k] - 1), {k, 2, n}], {n, 1, 41}]  (* Geoffrey Critzer, Jan 03 2012 *)

a(n) = sum(k = 2, n, -moebius(k) * (1 << (n\k) - 1)); \\ Amiram Eldar, May 09 2025

a(n) = Sum_{k=2..n} -A008683(k) * (2^floor(n/k)-1).
a(n) = 2^n - A085945(n) - 1 = A000225(n) - A085945(n);
a(n) - a(n-1) = 1 iff n is prime;
a(p^e) = a(p^e - 1) + 2^(p^(e-1) - 1) for p prime, e > 0;
a(p*q) = a(p*q - 1) + 2^(p-1) + 2^(q-1) - 1 for primes p <> q.

A282748 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 4, 3, 4, 1, 1, 2, 9, 4, 5, 1, 1, 6, 3, 16, 5, 6, 1, 1, 4, 15, 4, 25, 6, 7, 1, 1, 6, 9, 28, 5, 36, 7, 8, 1, 1, 4, 21, 16, 45, 6, 49, 8, 9, 1, 1, 10, 9, 52, 25, 66, 7, 64, 9, 10, 1, 1, 4, 39, 16, 105, 36, 91, 8, 81, 10, 11, 1, 1, 12, 9, 100, 25, 186, 49, 120, 9, 100, 11, 12, 1, 1, 6, 45, 16, 205, 36, 301, 64, 153, 10, 121, 12, 13, 1

Offset: 1

N. J. A. Sloane, Mar 05 2017

See A101391 for the triangle T(n,k) = number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_1,x_2,...,x_k) = 1 (2 <= k <= n).

			Triangle begins:
  1;
  1,  1;
  1,  2,  1;
  1,  2,  3,   1;
  1,  4,  3,   4,   1;
  1,  2,  9,   4,   5,   1;
  1,  6,  3,  16,   5,   6,  1;
  1,  4, 15,   4,  25,   6,  7,   1;
  1,  6,  9,  28,   5,  36,  7,   8,  1;
  1,  4, 21,  16,  45,   6, 49,   8,  9,   1;
  1, 10,  9,  52,  25,  66,  7,  64,  9,  10,  1;
  1,  4, 39,  16, 105,  36, 91,   8, 81,  10, 11,  1;
  1, 12,  9, 100,  25, 186, 49, 120,  9, 100, 11, 12, 1;
  ...
From _Gus Wiseman_, Nov 12 2020: (Start)
Row n = 6 counts the following compositions:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (51)  (123)  (1131)  (11121)
             (132)  (1311)  (11211)
             (141)  (3111)  (12111)
             (213)          (21111)
             (231)
             (312)
             (321)
             (411)
(End)

Alois P. Heinz, Rows n = 1..200, flattened (first 100 rows from Chai Wah Wu)
Temba Shonhiwa, Compositions with pairwise relatively prime summands within a restricted setting, Fibonacci Quart. 44 (2006), no. 4, 316-323.

A072704 counts the unimodal instead of coprime version.
A087087 and A335235 rank these compositions.
A101268 gives row sums.
A101391 is the relatively prime instead of pairwise coprime version.
A282749 is the unordered version.
A000740 counts relatively prime compositions, with strict case A332004.
A007360 counts pairwise coprime or singleton strict partitions.
A051424 counts pairwise coprime or singleton partitions, ranked by A302569.
A097805 counts compositions by sum and length.
A178472 counts compositions with a common divisor.
A216652 and A072574 count strict compositions by sum and length.
A305713 counts pairwise coprime strict partitions.
A327516 counts pairwise coprime partitions, ranked by A302696.
A335235 ranks pairwise coprime or singleton compositions.
A337462 counts pairwise coprime compositions, ranked by A333227.
A337562 counts pairwise coprime or singleton strict compositions.
A337665 counts compositions whose distinct parts are pairwise coprime, ranked by A333228.
Cf. A000837, A007359, A302568, A337461, A337561, A337667.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n,{k}],Length[#]==1||CoprimeQ@@#&]],{n,10},{k,n}] (* Gus Wiseman, Nov 12 2020 *)

It seems that no general formula or recurrence is known, although Shonhiwa gives formulas for a few of the early diagonals.

A329145 Number of non-necklace compositions of n.

Original entry on oeis.org

0, 0, 1, 3, 9, 19, 45, 93, 197, 405, 837, 1697, 3465, 7011, 14193, 28653, 57825, 116471, 234549, 471801, 948697, 1906407, 3829581, 7689357, 15435033, 30973005, 62137797, 124630149, 249922665, 501078345, 1004468157, 2013263853, 4034666121, 8084640465

Offset: 1

Gus Wiseman, Nov 10 2019

nonn

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

			The a(3) = 1 through a(6) = 19 compositions:
  (21)  (31)   (32)    (42)
        (121)  (41)    (51)
        (211)  (131)   (141)
               (212)   (213)
               (221)   (231)
               (311)   (312)
               (1121)  (321)
               (1211)  (411)
               (2111)  (1131)
                       (1221)
                       (1311)
                       (2112)
                       (2121)
                       (2211)
                       (3111)
                       (11121)
                       (11211)
                       (12111)
                       (21111)

Numbers whose prime signature is not a necklace are A329142.
Binary necklaces are A000031.
Necklace compositions are A008965.
Lyndon compositions are A059966.
Numbers whose reversed binary expansion is a necklace are A328595.
Cf. A000740, A001037, A019536, A070211, A178472, A318731, A329138, A329141.

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

a(n) = 2^(n-1) - A008965(n).

A247146 As a binary numeral, the bit 2^(m-1) of a(n) is 1 iff m is a proper divisor of n.

Original entry on oeis.org

0, 1, 1, 3, 1, 7, 1, 11, 5, 19, 1, 47, 1, 67, 21, 139, 1, 295, 1, 539, 69, 1027, 1, 2223, 17, 4099, 261, 8267, 1, 16951, 1, 32907, 1029, 65539, 81, 133423, 1, 262147, 4101, 524955, 1, 1056871, 1, 2098187, 16661, 4194307, 1, 8423599, 65, 16777747, 65541

Offset: 1

Morgan L. Owens, Nov 21 2014

nonn

a(n)==1 iff n is prime.
Apparently Moebius transform of A178472.
For n>1, the binary representation of a(n) is given by row (n-1) of A077049 (when read as a triangular array). - Tom Edgar, Nov 28 2014

Cf. A034729, A077049, A178472.

With[{n=Range[100]},(1/2) ((Total/@(2^Divisors[n])) - 2^n)]

a(n) = sumdiv(n, k, 2^(k-1)) - 2^(n-1); \\ Michel Marcus, Nov 25 2014

from sympy import divisors
def A247146(n): return sum(1<Chai Wah Wu, Jul 15 2022

a(n) = A034729(n) - 2^(n-1). - Michel Marcus, Nov 22 2014

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

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 3, 1, 3, 3, 5, 1, 13, 1, 13, 7, 19, 1, 59, 1, 59, 15, 65, 1, 309, 5, 133, 27, 195, 1, 2883, 1, 435, 67, 617, 17, 4133, 1, 1177, 135, 2915, 1, 36647, 1, 3299, 1767, 4757, 1, 52045, 13, 21149, 619, 11307, 1, 187307, 69, 29467, 1179, 30461

Offset: 0

Ilya Gutkovskiy, Feb 04 2020

nonn

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

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

Cf. A032020, A100347, A121998, A178472, A331885, A331887, A331888, A332002.

a:= proc(n) local b; b:=
      proc(m, i, p) option remember; `if`(m=0, p!, `if`(i<1, 0,
        b(m, i-1, p)+`if`(i>m or igcd(i, n)=1, 0, b(m-i, i-1, p+1))))
      end; forget(b): b(n$2, 0)
    end:
seq(a(n), n=0..63);  # Alois P. Heinz, Feb 04 2020

a[n_] := Module[{b}, b[m_, i_, p_] := b[m, i, p] = If[m == 0, p!, If[i < 1, 0, b[m, i - 1, p] + If[i > m || GCD[i, n] == 1, 0, b[m - i, i - 1, p + 1]]]]; b[n, n, 0]];
a /@ Range[0, 63] (* Jean-François Alcover, Nov 26 2020, after Alois P. Heinz *)

A338554 Number of non-constant integer partitions of n whose parts have a common divisor > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 2, 1, 5, 0, 9, 0, 13, 6, 18, 0, 33, 0, 40, 14, 54, 0, 87, 5, 99, 27, 133, 0, 211, 0, 226, 55, 295, 18, 443, 0, 488, 100, 637, 0, 912, 0, 1000, 198, 1253, 0, 1775, 13, 1988, 296, 2434, 0, 3358, 59, 3728, 489, 4563, 0, 6241, 0, 6840, 814

Offset: 0

Gus Wiseman, Nov 07 2020

nonn

			The a(6) = 2 through a(15) = 6 partitions (empty columns indicated by dots, A = 10, B = 11, C = 12):
  (42)  .  (62)   (63)  (64)    .  (84)     .  (86)      (96)
           (422)        (82)       (93)        (A4)      (A5)
                        (442)      (A2)        (C2)      (C3)
                        (622)      (633)       (644)     (663)
                        (4222)     (642)       (662)     (933)
                                   (822)       (842)     (6333)
                                   (4422)      (A22)
                                   (6222)      (4442)
                                   (42222)     (6422)
                                               (8222)
                                               (44222)
                                               (62222)
                                               (422222)

A046022 lists positions of zeros.
A082023(n) - A059841(n) is the 2-part version, n > 2.
A303280(n) - 1 is the strict case (n > 1).
A338552 lists the Heinz numbers of these partitions.
A338553 counts the complement, with Heinz numbers A338555.
A000005 counts constant partitions, with Heinz numbers A000961.
A000837 counts relatively prime partitions, with Heinz numbers A289509.
A018783 counts non-relatively prime partitions (ordered: A178472), with Heinz numbers A318978.
A282750 counts relatively prime partitions by sum and length.
Cf. A000010, A008284, A051424, A082024, A289508, A302698, A304712.

Table[Length[Select[IntegerPartitions[n],!SameQ@@#&&GCD@@#>1&]],{n,0,30}]

For n > 0, a(n) = A018783(n) - A000005(n) + 1.

A304623 Regular triangle where T(n,k) is the number of aperiodic multisets with maximum k that fit within some normal multiset of weight n.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 1, 6, 11, 8, 1, 10, 21, 27, 16, 1, 12, 38, 61, 63, 32, 1, 18, 57, 120, 162, 143, 64, 1, 22, 87, 205, 347, 409, 319, 128, 1, 28, 122, 333, 651, 950, 1000, 703, 256, 1, 32, 164, 506, 1132, 1926, 2504, 2391, 1535, 512, 1, 42, 217, 734, 1840

Offset: 1

Gus Wiseman, May 15 2018

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

			Triangle begins:
1
1    2
1    4    4
1    6   11    8
1   10   21   27   16
1   12   38   61   63   32
1   18   57  120  162  143   64
1   22   87  205  347  409  319  128
The a(4,3) = 11 multisets are (3), (13), (23), (113), (123), (133), (223), (233), (1123), (1223), (1233).

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

Row sums are A303976.

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

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&],Max],{n,10}]

T(n,k) = sum(j=1, n, sumdiv(j, d, sum(i=max(1, j+k-n), d, moebius(j/d)*binomial(k-1, i-1)*binomial(d-1, i-1)))) \\ Andrew Howroyd, Jan 20 2023

T(n,k) = Sum_{j=1..n} Sum_{d|j} Sum_{i=max(1, j+k-n)..d} mu(j/d)*binomial(k-1, i-1)*binomial(d-1, i-1). - Andrew Howroyd, Jan 20 2023

A304648 Number of different periodic multisets that fit within some normal multiset of weight n.

Original entry on oeis.org

0, 1, 3, 7, 13, 25, 44, 78, 136, 242, 422, 747, 1314, 2326, 4121, 7338, 13052, 23288, 41568, 74329, 133011, 238338, 427278, 766652, 1376258, 2472012, 4441916, 7984990, 14358424, 25826779, 46465956, 83616962, 150497816, 270917035, 487753034, 878244512

Offset: 1

Gus Wiseman, May 15 2018

nonn

A multiset is normal if it spans an initial interval of positive integers. It is periodic if its multiplicities have a common divisor greater than 1.

			The a(5) = 13 periodic multisets:
(11), (22), (33), (44),
(111), (222), (333),
(1111), (1122), (1133), (2222), (2233),
(11111).

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

Cf. A000217, A001597, A018783, A027941, A178472, A210554, A303547, A303709, A303974, A303976.

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=2, n, -moebius(d)*x^d/(1 - x - x^d*(2-x)) + O(x*x^n))/(1-x), -n) \\ Andrew Howroyd, Feb 04 2021

From Andrew Howroyd, Feb 04 2021: (Start)
a(n) = A027941(n) - A303976(n).
G.f.: Sum_{d>=2} -mu(d)*x^d/((1 - x - x^d*(2-x))*(1-x)).
(End)

a(12)-a(13) from Robert Price, Sep 15 2018

Terms a(14) and beyond from Andrew Howroyd, Feb 04 2021

A356353 Numbers k such that A356352(k) <> 1.

Original entry on oeis.org

0, 3, 7, 12, 15, 31, 48, 51, 56, 60, 63, 127, 192, 195, 204, 207, 240, 243, 252, 255, 448, 455, 504, 511, 768, 771, 780, 783, 816, 819, 828, 831, 960, 963, 972, 975, 992, 1008, 1011, 1020, 1023, 2047, 3072, 3075, 3084, 3087, 3120, 3123, 3132, 3135, 3264, 3267

Offset: 1

Rémy Sigrist, Oct 15 2022

Also, numbers whose binary expansions are juxtapositions of constant blocks of size g > 1.
A001196 and A097254 are subsequences.
There are A178472(k) terms with binary length k.

			The first terms, alongside their binary expansions and A356352(a(n)), are:
  n   a(n)  bin(a(n))   A356352(a(n))
  --  ----  ----------  -------------
   1     0           0              0
   2     3          11              2
   3     7         111              3
   4    12        1100              2
   5    15        1111              4
   6    31       11111              5
   7    48      110000              2
   8    51      110011              2
   9    56      111000              3
  10    60      111100              2
  11    63      111111              6
  12   127     1111111              7
  13   192    11000000              2
  14   195    11000011              2
  15   204    11001100              2
  16   207    11001111              2

Rémy Sigrist, PARI program
Index entries for sequences related to binary expansion of n

Cf. A001196, A097254, A178472, A356352.

is(n) = { my (r=[]); while (n, my (v=valuation(n+n%2, 2)); n\=2^v; r=concat(v, r)); gcd(r)!=1 }

PARI
```
See Links section.
```

from math import gcd
from itertools import groupby
def ok(n):
    if n == 0: return True # by convention of A356352
    return gcd(*(len(list(g)) for k, g in groupby(bin(n)[2:]))) != 1
print([k for k in range(3268) if ok(k)]) # Michael S. Branicky, Oct 15 2022

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A109511 Number of subsets of the first n numbers having a common divisor greater than 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A282748 Triangle read by rows: T(n,k) is the number of compositions of n into k parts x_1, x_2, ..., x_k such that gcd(x_i, x_j) = 1 for all i != j (where 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A329145 Number of non-necklace compositions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A247146 As a binary numeral, the bit 2^(m-1) of a(n) is 1 iff m is a proper divisor of n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A338554 Number of non-constant integer partitions of n whose parts have a common divisor > 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A304623 Regular triangle where T(n,k) is the number of aperiodic multisets with maximum k that fit within some normal multiset of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs