Search: a328460 -id:a328460
|
| |
|
|
A178470
|
|
Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.
|
|
+10
27
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
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)
|
|
|
MAPLE
|
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)):
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(PARI) 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]))
|
|
|
CROSSREFS
|
Partitions with all pairs of consecutive parts relatively prime are A328172.
Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A087086
|
|
Primitive sets of integers, each subset mapped onto a unique binary integer, values here shown in decimal.
|
|
+10
14
|
|
|
|
0, 1, 2, 4, 6, 8, 12, 16, 18, 20, 22, 24, 28, 32, 40, 48, 56, 64, 66, 68, 70, 72, 76, 80, 82, 84, 86, 88, 92, 96, 104, 112, 120, 128, 132, 144, 148, 160, 176, 192, 196, 208, 212, 224, 240, 256, 258, 264, 272, 274, 280, 288, 296, 304, 312, 320, 322, 328, 336, 338, 344
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
A primitive set of integers has no pair of elements one of which divides the other. Each element i in a subset contributes 2^(i-1) to the binary value for that subset. The integers missing from the sequence correspond to nonprimitive subsets.
|
|
|
REFERENCES
|
Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(10)=22 since the 10th primitive set counting from 0 is {5,3,2}, which maps onto 10110 binary = 22 decimal.
From Gus Wiseman, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
0: 0 ~ {}
1: 1 ~ {1}
2: 10 ~ {2}
4: 100 ~ {3}
6: 110 ~ {2,3}
8: 1000 ~ {4}
12: 1100 ~ {3,4}
16: 10000 ~ {5}
18: 10010 ~ {2,5}
20: 10100 ~ {3,5}
22: 10110 ~ {2,3,5}
24: 11000 ~ {4,5}
28: 11100 ~ {3,4,5}
(End)
|
|
|
MATHEMATICA
|
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Select[Range[0, 100], stableQ[Join@@Position[Reverse[IntegerDigits[#, 2]], 1], Divisible]&] (* Gus Wiseman, Oct 31 2019 *)
|
|
|
CROSSREFS
|
A051026 gives the number of primitive subsets of the integers 1 to n.
The version for prime indices (rather than binary indices) is A316476.
The relatively prime case is A328671.
Partitions with no consecutive divisible parts are A328171.
Compositions without consecutive divisible parts are A328460.
A ranking of antichains is A326704.
|
|
|
KEYWORD
|
easy,nonn,base
|
|
|
AUTHOR
|
Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 14 2003
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328598
|
|
Number of compositions of n with no part circularly followed by a divisor.
|
|
+10
12
|
|
|
|
1, 0, 0, 0, 0, 2, 0, 4, 2, 7, 12, 11, 22, 26, 55, 63, 99, 149, 215, 324, 458, 699, 1006, 1492, 2185, 3202, 4734, 6928, 10242, 14951, 22023, 32365, 47557, 69905, 102633, 150983, 221712, 325918, 478841, 703647, 1034103, 1519431, 2233061, 3281003, 4821790, 7085358
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
A composition of n is a finite sequence of positive integers summing to n.
Circularity means the last part is followed by the first.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The a(5) = 2 through a(12) = 22 compositions (empty column not shown):
(2,3) (2,5) (3,5) (2,7) (3,7) (2,9) (5,7)
(3,2) (3,4) (5,3) (4,5) (4,6) (3,8) (7,5)
(4,3) (5,4) (6,4) (4,7) (2,3,7)
(5,2) (7,2) (7,3) (5,6) (2,7,3)
(2,4,3) (2,3,5) (6,5) (3,2,7)
(3,2,4) (2,5,3) (7,4) (3,4,5)
(4,3,2) (3,2,5) (8,3) (3,5,4)
(3,5,2) (9,2) (3,7,2)
(5,2,3) (2,4,5) (4,3,5)
(5,3,2) (4,5,2) (4,5,3)
(2,3,2,3) (5,2,4) (5,3,4)
(3,2,3,2) (5,4,3)
(7,2,3)
(7,3,2)
(2,3,2,5)
(2,3,4,3)
(2,5,2,3)
(3,2,3,4)
(3,2,5,2)
(3,4,3,2)
(4,3,2,3)
(5,2,3,2)
|
|
|
MATHEMATICA
|
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@Not/@Divisible@@@Partition[#, 2, 1, 1]&]], {n, 0, 10}]
|
|
|
PROG
|
(PARI)
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)={concat([1], sum(k=1, n, b(n, k, (i, j)->i%j<>0)))} \\ Andrew Howroyd, Oct 26 2019
|
|
|
CROSSREFS
|
The version with singletons is A318726.
The non-circular version is A328460.
Also forbidding parts circularly followed by a multiple gives A328599.
Partitions with no part followed by a divisor are A328171.
Cf. A000740, A008965, A167606, A178470, A318748, A328187, A328508, A328593, A328597, A328601, A328603, A328609.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328508
|
|
Number of compositions of n with no part divisible by the next or the prior.
|
|
+10
10
|
|
|
|
1, 1, 1, 1, 1, 3, 1, 6, 4, 8, 14, 14, 27, 30, 55, 69, 97, 155, 200, 312, 421, 630, 893, 1260, 1864, 2600, 3813, 5395, 7801, 11196, 15971, 23126, 32917, 47514, 67993, 97670, 140334, 200913, 289147, 414119, 595109, 853751, 1225086, 1759405, 2523151, 3623984, 5198759
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The a(1) = 1 through a(11) = 14 compositions (A = 10, B = 11):
(1) (2) (3) (4) (5) (6) (7) (8) (9) (A) (B)
(23) (25) (35) (27) (37) (29)
(32) (34) (53) (45) (46) (38)
(43) (323) (54) (64) (47)
(52) (72) (73) (56)
(232) (234) (235) (65)
(252) (253) (74)
(432) (325) (83)
(343) (92)
(352) (254)
(523) (272)
(532) (353)
(2323) (434)
(3232) (452)
|
|
|
MATHEMATICA
|
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, x_, y_, ___}/; Divisible[y, x]||Divisible[x, y]]&]], {n, 0, 10}]
|
|
|
PROG
|
(PARI) seq(n)={my(r=matid(n)); for(k=1, n, for(i=1, k-1, r[i, k]=sum(j=1, k-i, if(i%j && j%i, r[j, k-i])))); concat([1], vecsum(Col(r)))} \\ Andrew Howroyd, Oct 19 2019
|
|
|
CROSSREFS
|
If we only forbid parts to be divisible by the next, we get A328460.
Compositions with each part relatively prime to the next are A167606.
Compositions with no part relatively prime to the next are A178470.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328593
|
|
Numbers whose binary indices have no consecutive divisible parts.
|
|
+10
10
|
|
|
|
0, 1, 2, 4, 6, 8, 12, 14, 16, 18, 20, 22, 24, 28, 30, 32, 40, 44, 46, 48, 50, 52, 54, 56, 60, 62, 64, 66, 68, 70, 72, 76, 78, 80, 82, 84, 86, 88, 92, 94, 96, 104, 108, 110, 112, 114, 116, 118, 120, 124, 126, 128, 132, 134, 144, 146, 148, 150, 152, 156, 158, 160
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The sequence of terms together with their binary expansions and binary indices begins:
0: 0 ~ {}
1: 1 ~ {1}
2: 10 ~ {2}
4: 100 ~ {3}
6: 110 ~ {2,3}
8: 1000 ~ {4}
12: 1100 ~ {3,4}
14: 1110 ~ {2,3,4}
16: 10000 ~ {5}
18: 10010 ~ {2,5}
20: 10100 ~ {3,5}
22: 10110 ~ {2,3,5}
24: 11000 ~ {4,5}
28: 11100 ~ {3,4,5}
30: 11110 ~ {2,3,4,5}
32: 100000 ~ {6}
40: 101000 ~ {4,6}
44: 101100 ~ {3,4,6}
46: 101110 ~ {2,3,4,6}
48: 110000 ~ {5,6}
50: 110010 ~ {2,5,6}
|
|
|
MATHEMATICA
|
Select[Range[0, 100], !MatchQ[Join@@Position[Reverse[IntegerDigits[#, 2]], 1], {___, x_, y_, ___}/; Divisible[y, x]]&]
|
|
|
CROSSREFS
|
The version for prime indices is A328603.
Numbers with no successive binary indices are A003714.
Partitions with no consecutive divisible parts are A328171.
Compositions without consecutive divisible parts are A328460.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328600
|
|
Number of necklace compositions of n with no part circularly followed by a divisor.
|
|
+10
10
|
|
|
|
0, 0, 0, 0, 1, 0, 2, 1, 3, 5, 5, 7, 10, 18, 20, 29, 40, 58, 78, 111, 156, 218, 304, 429, 604, 859, 1209, 1726, 2423, 3462, 4904, 7000, 9953, 14210, 20270, 28979, 41391, 59253, 84799, 121539, 174162, 249931, 358577, 515090, 739932, 1063826, 1529766, 2201382, 3168565
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,7
|
|
|
COMMENTS
|
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.
Circularity means the last part is followed by the first.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The a(5) = 1 through a(13) = 18 necklace compositions (empty column not shown):
(2,3) (2,5) (3,5) (2,7) (3,7) (2,9) (5,7) (4,9)
(3,4) (4,5) (4,6) (3,8) (2,3,7) (5,8)
(2,4,3) (2,3,5) (4,7) (2,7,3) (6,7)
(2,5,3) (5,6) (3,4,5) (2,11)
(2,3,2,3) (2,4,5) (3,5,4) (3,10)
(2,3,2,5) (2,4,7)
(2,3,4,3) (2,6,5)
(2,8,3)
(3,6,4)
(2,3,5,3)
|
|
|
MATHEMATICA
|
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@Not/@Divisible@@@Partition[#, 2, 1, 1]&]], {n, 10}]
|
|
|
PROG
|
(PARI)
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)->i%j<>0))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019
|
|
|
CROSSREFS
|
The non-necklace version is A328598.
The version with singletons is A318729.
The case forbidding multiples as well as divisors is A328601.
The non-necklace, non-circular version is A328460.
The version for co-primality (instead of divisibility) is A328602.
Partitions with no part followed by a divisor are A328171.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328601
|
|
Number of necklace compositions of n with no part circularly followed by a divisor or a multiple.
|
|
+10
10
|
|
|
|
0, 0, 0, 0, 1, 0, 2, 1, 2, 5, 4, 7, 6, 13, 14, 20, 30, 38, 50, 68, 97, 132, 176, 253, 328, 470, 631, 901, 1229, 1709, 2369, 3269, 4590, 6383, 8897, 12428, 17251, 24229, 33782, 47404, 66253, 92859, 130141, 182468, 256261, 359675, 505230, 710058, 997952, 1404214
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,7
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The a(5) = 1 through a(13) = 6 necklace compositions (empty column not shown):
(2,3) (2,5) (3,5) (2,7) (3,7) (2,9) (5,7) (4,9)
(3,4) (4,5) (4,6) (3,8) (2,3,7) (5,8)
(2,3,5) (4,7) (2,7,3) (6,7)
(2,5,3) (5,6) (3,4,5) (2,11)
(2,3,2,3) (3,5,4) (3,10)
(2,3,2,5) (2,3,5,3)
(2,3,4,3)
|
|
|
MATHEMATICA
|
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@Not/@Divisible@@@Partition[#, 2, 1, 1]&&And@@Not/@Divisible@@@Reverse/@Partition[#, 2, 1, 1]&]], {n, 10}]
|
|
|
PROG
|
(PARI)
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)->i%j<>0 && j%i<>0))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019
|
|
|
CROSSREFS
|
The non-necklace version is A328599.
The case forbidding divisors only is A328600 or A318729 (with singletons).
The non-necklace, non-circular version is A328508.
The version for co-primality (instead of indivisibility) is A328597.
Cf. A000740, A008965, A032153, A167606, A318748, A328171, A328460, A328593, A328598, A328602, A328603, A328608, A328609.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
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.
|
|
+10
9
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
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}
|
|
|
MATHEMATICA
|
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]]&]
|
|
|
CROSSREFS
|
These are the Heinz numbers of the partitions counted by A328171.
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.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328677
|
|
Numbers whose distinct prime indices are relatively prime and pairwise indivisible.
|
|
+10
9
|
|
|
|
2, 4, 8, 15, 16, 32, 33, 35, 45, 51, 55, 64, 69, 75, 77, 85, 93, 95, 99, 119, 123, 128, 135, 141, 143, 145, 153, 155, 161, 165, 175, 177, 187, 201, 205, 207, 209, 215, 217, 219, 221, 225, 245, 249, 253, 255, 256, 265, 275, 279, 287, 291, 295, 297, 309, 323
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
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. Stable numbers are listed in A316476.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The sequence of terms together with their prime indices begins:
2: {1}
4: {1,1}
8: {1,1,1}
15: {2,3}
16: {1,1,1,1}
32: {1,1,1,1,1}
33: {2,5}
35: {3,4}
45: {2,2,3}
51: {2,7}
55: {3,5}
64: {1,1,1,1,1,1}
69: {2,9}
75: {2,3,3}
77: {4,5}
85: {3,7}
93: {2,11}
95: {3,8}
99: {2,2,5}
119: {4,7}
|
|
|
MATHEMATICA
|
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Select[Range[100], GCD@@primeMS[#]==1&&stableQ[primeMS[#], Divisible]&]
|
|
|
CROSSREFS
|
These are the Heinz numbers of the partitions counted by A328676.
Numbers whose prime indices are relatively prime are A289509.
Partitions whose distinct parts are pairwise indivisible are A305148.
The version for binary indices (instead of prime indices) is A328671.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A328599
|
|
Number of compositions of n with no part circularly followed by a divisor or a multiple.
|
|
+10
8
|
|
|
|
1, 0, 0, 0, 0, 2, 0, 4, 2, 4, 12, 8, 22, 14, 36, 44, 62, 114, 130, 206, 264, 414, 602, 822, 1250, 1672, 2520, 3518, 5146, 7408, 10448, 15224, 21496, 31284, 44718, 64170, 92314, 131618, 190084, 271870, 391188, 560978, 804264, 1155976, 1656428, 2381306, 3414846
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
A composition of n is a finite sequence of positive integers summing to n.
Circularity means the last part is followed by the first.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
The a(0) = 1 through a(12) = 22 compositions (empty columns not shown):
() (2,3) (2,5) (3,5) (2,7) (3,7) (2,9) (5,7)
(3,2) (3,4) (5,3) (4,5) (4,6) (3,8) (7,5)
(4,3) (5,4) (6,4) (4,7) (2,3,7)
(5,2) (7,2) (7,3) (5,6) (2,7,3)
(2,3,5) (6,5) (3,2,7)
(2,5,3) (7,4) (3,4,5)
(3,2,5) (8,3) (3,5,4)
(3,5,2) (9,2) (3,7,2)
(5,2,3) (4,3,5)
(5,3,2) (4,5,3)
(2,3,2,3) (5,3,4)
(3,2,3,2) (5,4,3)
(7,2,3)
(7,3,2)
(2,3,2,5)
(2,3,4,3)
(2,5,2,3)
(3,2,3,4)
(3,2,5,2)
(3,4,3,2)
(4,3,2,3)
(5,2,3,2)
|
|
|
MATHEMATICA
|
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@Not/@Divisible@@@Partition[#, 2, 1, 1]&&And@@Not/@Divisible@@@Reverse/@Partition[#, 2, 1, 1]&]], {n, 0, 10}]
|
|
|
PROG
|
(PARI)
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)={concat([1], sum(k=1, n, b(n, k, (i, j)->i%j<>0&&j%i<>0)))} \\ Andrew Howroyd, Oct 26 2019
|
|
|
CROSSREFS
|
The case forbidding only divisors (not multiples) is A328598.
The non-circular version is A328508.
Partitions with no part followed by a divisor are A328171.
Cf. A000740, A008965, A167606, A318729, A318748, A328460, A328593, A328600, A328603, A328608, A328609, A328674.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.010 seconds
|
