A328336 -id:A328336 - cp's OEIS frontend

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

1, 1, 1, 1, 2, 1, 5, 1, 8, 4, 17, 3, 38, 5, 67, 25, 132, 27, 290, 54, 547, 163, 1086, 255, 2277, 530, 4416, 1267, 8850, 2314, 18151, 4737, 35799, 10499, 71776, 20501, 145471, 41934, 289695, 89030, 581117, 178424, 1171545, 365619, 2342563, 761051, 4699711

Offset: 0

Franklin T. Adams-Watters, May 28 2010

nonn

A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.

a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler.

			The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
From _Gus Wiseman_, Nov 19 2019: (Start)
The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
  1  2  3  4   5  6    7  8     9    A      B
           22     24      26    36   28     263
                  33      44    63   46     362
                  42      62    333  55
                  222     224        64
                          242        82
                          422        226
                          2222       244
                                     262
                                     424
                                     442
                                     622
                                     2224
                                     2242
                                     2422
                                     4222
                                     22222
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The case of partitions is A328187, with Heinz numbers A328336.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
Cf. A000837, A003242, A018783, A167606, A178471, A178472, A328171, A328188, A328220.

b:= proc(n, h) option remember; `if`(n=0, 1,
      add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
    end:
a:= n-> `if`(n=1, 1, b(n, 1)):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 23 2011

b[n_, h_] := b[n, h] = If[n == 0, 1, Sum [If[h == 1 || GCD[j, h] > 1, b[n - j, j], 0], {j, 2, n}]]; a[n_] := If[n == 1, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,20}] (* Gus Wiseman, Nov 19 2019 *)

am(n)=local(r);r=matrix(n,n,i,j,i==j);for(i=2,n,for(j=1,i-1,for(k=1,j,if(gcd(i-j,k)>1,r[i,i-j]+=r[j,k]))));r
al(n)=local(m);m=am(n);vector(n,i,sum(j=1,i,m[i,j]))

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 3, 38, 4, 46, 19, 58, 9, 94, 18, 106, 41, 144, 28, 221, 37, 246, 92, 318, 87, 465, 95, 530, 198, 693, 169, 963, 220, 1108, 424, 1383, 381, 1899, 492, 2216, 815, 2732, 799, 3644, 1041, 4231, 1585, 5194, 1608

Offset: 0

Gus Wiseman, Oct 12 2019

nonn

			The a(1) = 1 through a(15) = 9 partitions (A..F = 10..15):
  1  2  3  4   5  6    7  8     9    A      B  C       D  E        F
           22     33      44    63   55        66         77       96
                  42      62    333  64        84         86       A5
                  222     422        82        93         A4       C3
                          2222       442       A2         C2       555
                                     622       444        644      663
                                     4222      633        662      933
                                     22222     642        842      6333
                                               822        A22      33333
                                               3333       4442
                                               4422       6422
                                               6222       8222
                                               42222      44222
                                               222222     62222
                                                          422222
                                                          2222222

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..300

The Heinz numbers of these partitions are given by A328336.
The case of compositions is A178470.
The strict case is A328220.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Cf. A000837, A018783, A328028, A328170, A328171, A328188.

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A328867 Heinz numbers of integer partitions in which no two distinct parts are relatively prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 21, 23, 25, 27, 29, 31, 32, 37, 39, 41, 43, 47, 49, 53, 57, 59, 61, 63, 64, 65, 67, 71, 73, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 111, 113, 115, 117, 121, 125, 127, 128, 129, 131, 133, 137, 139, 147, 149

Offset: 1

Gus Wiseman, Oct 30 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

A partition with no two distinct parts relatively prime is said to be intersecting.

			The sequence of terms together with their prime indices begins:
    1: {}
    2: {1}
    3: {2}
    4: {1,1}
    5: {3}
    7: {4}
    8: {1,1,1}
    9: {2,2}
   11: {5}
   13: {6}
   16: {1,1,1,1}
   17: {7}
   19: {8}
   21: {2,4}
   23: {9}
   25: {3,3}
   27: {2,2,2}
   29: {10}
   31: {11}
   32: {1,1,1,1,1}

These are the Heinz numbers of the partitions counted by A328673.
The strict case is A318719.
The relatively prime version is A328868.
A ranking using binary indices is A326910.
The version for non-isomorphic multiset partitions is A319752.
The version for divisibility (instead of relative primality) is A316476.
Cf. A000837, A056239, A112798, A200976, A289509, A303283, A305843, A318715, A318716, A328336.

Select[Range[100],And@@(GCD[##]>1&)@@@Subsets[PrimePi/@First/@FactorInteger[#],{2}]&]

A328335 Numbers whose consecutive prime indices are relatively prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 48, 51, 52, 53, 55, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88

Offset: 1

Gus Wiseman, Oct 14 2019

nonn

First differs from A302569 in having 105, which has prime indices {2, 3, 4}.
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.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are Heinz numbers of partitions whose consecutive parts are relatively prime (A328172).

			The sequence of terms together with their prime indices begins:
   1: {}
   2: {1}
   3: {2}
   4: {1,1}
   5: {3}
   6: {1,2}
   7: {4}
   8: {1,1,1}
  10: {1,3}
  11: {5}
  12: {1,1,2}
  13: {6}
  14: {1,4}
  15: {2,3}
  16: {1,1,1,1}
  17: {7}
  19: {8}
  20: {1,1,3}
  22: {1,5}
  23: {9}

A superset of A302569.
Numbers whose prime indices are relatively prime are A289509.
Numbers with no consecutive prime indices relatively prime are A328336.
Cf. A000837, A056239, A112798, A281116, A289508, A318981, A328168, A328169, A328172, A328187, A328188, A328220.

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

A337694 Numbers with no two relatively prime prime indices.

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 27, 29, 31, 37, 39, 41, 43, 47, 49, 53, 57, 59, 61, 63, 65, 67, 71, 73, 79, 81, 83, 87, 89, 91, 97, 101, 103, 107, 109, 111, 113, 115, 117, 121, 125, 127, 129, 131, 133, 137, 139, 147, 149, 151, 157, 159, 163, 167, 169, 171, 173, 179, 181, 183, 185, 189, 191, 193, 197, 199

Offset: 1

Gus Wiseman, Sep 23 2020

nonn

First differs from A305078 in having 1 and lacking 195.
First differs from A305103 in having 1 and 169 and lacking 195.
First differs from A328336 in lacking 897, with prime indices (2,6,9).
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.
Also Heinz numbers of integer partitions in which no two parts are relatively prime. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The sequence of terms together with their prime indices begins:
   1: {}      37: {12}     79: {22}      121: {5,5}
   3: {2}     39: {2,6}    81: {2,2,2,2} 125: {3,3,3}
   5: {3}     41: {13}     83: {23}      127: {31}
   7: {4}     43: {14}     87: {2,10}    129: {2,14}
   9: {2,2}   47: {15}     89: {24}      131: {32}
  11: {5}     49: {4,4}    91: {4,6}     133: {4,8}
  13: {6}     53: {16}     97: {25}      137: {33}
  17: {7}     57: {2,8}   101: {26}      139: {34}
  19: {8}     59: {17}    103: {27}      147: {2,4,4}
  21: {2,4}   61: {18}    107: {28}      149: {35}
  23: {9}     63: {2,2,4} 109: {29}      151: {36}
  25: {3,3}   65: {3,6}   111: {2,12}    157: {37}
  27: {2,2,2} 67: {19}    113: {30}      159: {2,16}
  29: {10}    71: {20}    115: {3,9}     163: {38}
  31: {11}    73: {21}    117: {2,2,6}   167: {39}

Robert Israel, Table of n, a(n) for n = 1..10000

A200976 and A328673 count these partitions.
A302696 and A302569 are pairwise coprime instead of pairwise non-coprime.
A318719 is the squarefree case.
A328867 looks at distinct prime indices.
A337666 is the version for standard compositions.
A101268 counts pairwise coprime or singleton compositions.
A318717 counts strict pairwise non-coprime partitions.
A327516 counts pairwise coprime partitions.
A333227 ranks pairwise coprime compositions.
A333228 ranks compositions whose distinct parts are pairwise coprime.
A335236 ranks compositions neither a singleton nor pairwise coprime.
A337462 counts pairwise coprime compositions.
A337667 counts pairwise non-coprime compositions.
Cf. A051185, A051424, A056239, A112798, A220377, A284825, A302797, A303282, A305843, A319752, A336737, A337599, A337604, A337605.

filter:= proc(n) local F,i,j,np;
  if n::even and n>2 then return false fi;
  F:= map(t -> numtheory:-pi(t[1]), ifactors(n)[2]);
  np:= nops(F);
  for i from 1 to np-1 do
    for j from i+1 to np do
      if igcd(F[i],F[j])=1 then return false fi
  od od;
  true
end proc:
select(filter, [$1..300]); # Robert Israel, Oct 06 2020

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
stabQ[u_,Q_]:=Array[#1==#2||!Q[u[[#1]],u[[#2]]]&,{Length[u],Length[u]},1,And];
Select[Range[100],stabQ[primeMS[#],CoprimeQ]&]

A328220 Number of strict integer partitions of n with no pair of consecutive parts relatively prime.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 3, 1, 5, 1, 5, 4, 6, 3, 10, 3, 11, 7, 12, 3, 19, 5, 18, 12, 23, 9, 36, 11, 33, 21, 40, 20, 58, 19, 58, 35, 70, 31, 98, 36, 101, 65, 112, 56, 155, 64, 164, 97, 188, 88, 250, 112, 256, 157, 293, 145, 392, 163, 399, 241, 461, 242

Offset: 0

Gus Wiseman, Oct 14 2019

nonn

			The a(2) = 1 through a(20) = 11 partitions (A..K = 10..20):
  2  3  4  5  6   7  8   9   A   B  C    D  E    F   G    H    I    J    K
              42     62  63  64     84      86   96  A6   863  A8   964  C8
                             82     93      A4   A5  C4   962  C6   A63  E6
                                    A2      C2   C3  E2        E4        F5
                                    642     842      862       F3        G4
                                                     A42       G2        I2
                                                               864       A64
                                                               963       A82
                                                               A62       C62
                                                               C42       E42
                                                                         8642

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..500

The non-strict case is A328187.
Partitions with all consecutive parts relatively prime are A328172, with strict case A328188.
Strict partitions with relatively prime parts are A078374.
Partitions with no consecutive divisibilities are A328171.
Cf. A000837, A018783, A070211, A289509, A318980, A325545, A328170, A328221, A328335, A328336.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]==1]&]],{n,0,30}]

A328603 Numbers whose prime indices have no consecutive divisible parts, meaning no prime index is a divisor of the next-smallest prime index, counted with multiplicity.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 51, 53, 55, 59, 61, 67, 69, 71, 73, 77, 79, 83, 85, 89, 91, 93, 95, 97, 101, 103, 105, 107, 109, 113, 119, 123, 127, 131, 137, 139, 141, 143, 145, 149, 151, 155, 157, 161, 163, 165, 167

Offset: 1

Gus Wiseman, Oct 26 2019

nonn

First differs from A304713 in having 105, with prime indices {2, 3, 4}.

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.

			The sequence of terms together with their prime indices begins:
    1: {}
    2: {1}
    3: {2}
    5: {3}
    7: {4}
   11: {5}
   13: {6}
   15: {2,3}
   17: {7}
   19: {8}
   23: {9}
   29: {10}
   31: {11}
   33: {2,5}
   35: {3,4}
   37: {12}
   41: {13}
   43: {14}
   47: {15}
   51: {2,7}

A subset of A005117.
These are the Heinz numbers of the partitions counted by A328171.
The non-strict version is A328674 (Heinz numbers for A328675).
The version for relatively prime instead of indivisible is A328335.
Compositions without consecutive divisibilities are A328460.
Numbers whose binary indices lack consecutive divisibilities are A328593.
The version with all pairs indivisible is A304713.
Cf. A056239, A112798, A316476, A318726, A318729, A326704, A328336, A328598, A328599.

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

Intersection of A005117 and A328674.

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 2, 69, 3, 111, 24, 190, 13, 384, 31, 646, 102, 1212, 113, 2348, 227, 4254, 613, 7993, 976, 15459, 1915, 28825, 4357, 54988, 7868, 105826, 15760, 201115, 33376, 385590, 63974, 744446, 128224, 1428047, 262914, 2754037

Offset: 1

Gus Wiseman, Oct 25 2019

nonn

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

Circularity means the last part is followed by the first.

			The a(2) = 1 through a(10) = 8 necklace compositions:
  (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)      (10)
            (2,2)       (2,4)         (2,6)      (3,6)    (2,8)
                        (3,3)         (4,4)      (3,3,3)  (4,6)
                        (2,2,2)       (2,2,4)             (5,5)
                                      (2,2,2,2)           (2,2,6)
                                                          (2,4,4)
                                                          (2,2,2,4)
                                                          (2,2,2,2,2)
The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).

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

The non-necklace, non-circular version is A178470.
The version for indivisibility (rather than co-primality) is A328600.
The circularly coprime (as opposed to anti-coprime) version is A328597.
Partitions with no consecutive parts relatively prime are A328187.
Cf. A000031, A000740, A008965, A032153, A318728, A318729, A318748, A328172, A328188, A328220, A328335, A328336, A328601, A328609.

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

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q,]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i,j)->gcd(i,j)<>1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019

Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019

A328868 Heinz numbers of integer partitions with no two (not necessarily distinct) parts relatively prime, but with no divisor in common to all of the parts.

Original entry on oeis.org

17719, 40807, 43381, 50431, 74269, 83143, 101543, 105703, 116143, 121307, 123469, 139919, 140699, 142883, 171613, 181831, 185803, 191479, 203557, 205813, 211381, 213239, 215267, 219271, 230347, 246703, 249587, 249899, 279371, 286897, 289007, 296993, 300847

Offset: 1

Gus Wiseman, Oct 30 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The sequence of terms together with their prime indices begins:
   17719: {6,10,15}
   40807: {6,14,21}
   43381: {6,15,20}
   50431: {10,12,15}
   74269: {6,10,45}
   83143: {10,15,18}
  101543: {6,21,28}
  105703: {6,15,40}
  116143: {12,14,21}
  121307: {10,15,24}
  123469: {12,15,20}
  139919: {6,15,50}
  140699: {6,22,33}
  142883: {6,10,75}
  171613: {6,14,63}
  181831: {6,20,45}
  185803: {10,14,35}
  191479: {14,18,21}
  203557: {15,18,20}
  205813: {10,15,36}
  211381: {10,12,45}
  213239: {6,15,70}
  215267: {6,10,105}
  219271: {6,26,39}
  230347: {6,6,10,15}

These are the Heinz numbers of the partitions counted by A202425.
Terms of A328679 that are not powers of 2.
The strict case is A318716 (preceded by 2).
A ranking using binary indices (instead of prime indices) is A326912.
Heinz numbers of relatively prime partitions are A289509.
Cf. A000837, A056239, A112798, A200976, A291166, A302796, A316476, A318715, A319752, A319759, A328336, A328672, A328677, A328867.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
dv=Select[Range[100000],GCD@@primeMS[#]==1&&And[And@@(GCD[##]>1&)@@@Tuples[Union[primeMS[#]],2]]&]

A328674 Numbers whose distinct prime indices have no consecutive divisible parts.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 19, 23, 25, 27, 29, 31, 32, 33, 35, 37, 41, 43, 45, 47, 49, 51, 53, 55, 59, 61, 64, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 113, 119, 121, 123, 125, 127, 128, 131, 135

Offset: 1

Gus Wiseman, Oct 29 2019

nonn

First differs from A316476 in having 105, with prime indices {2, 3, 4}.

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.

			The sequence of terms together with their prime indices begins:
    1: {}
    2: {1}
    3: {2}
    4: {1,1}
    5: {3}
    7: {4}
    8: {1,1,1}
    9: {2,2}
   11: {5}
   13: {6}
   15: {2,3}
   16: {1,1,1,1}
   17: {7}
   19: {8}
   23: {9}
   25: {3,3}
   27: {2,2,2}
   29: {10}
   31: {11}
   32: {1,1,1,1,1}
For example, 45 is in the sequence because its distinct prime indices are {2,3} and 2 is not a divisor of 3.

These are the Heinz numbers of the partitions counted by A328675.
The strict version is A328603.
Partitions without consecutive divisibilities are A328171.
Compositions without consecutive divisibilities are A328460.
Cf. A056239, A112798, A316476, A318729, A328335, A328336, A328593, A328598.

Select[Range[100],!MatchQ[PrimePi/@First/@FactorInteger[#],{_,x_,y_,_}/;Divisible[y,x]]&]

cp's OEIS Frontend

A178470 Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A328187 Number of integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A328867 Heinz numbers of integer partitions in which no two distinct parts are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A328335 Numbers whose consecutive prime indices are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337694 Numbers with no two relatively prime prime indices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A328220 Number of strict integer partitions of n with no pair of consecutive parts relatively prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A328603 Numbers whose prime indices have no consecutive divisible parts, meaning no prime index is a divisor of the next-smallest prime index, counted with multiplicity.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A328602 Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica