A304713 -id:A304713 - cp's OEIS frontend

A322438 Number of unordered pairs of factorizations of n into factors > 1 where no factor of one properly divides any factor of the other.

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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 4

Offset: 1

Gus Wiseman, Dec 08 2018

nonn

First differs from A322437 at a(144) = 4, A322437(144) = 3.

First differs from A379958 at a(120) = 2, A379958(120) = 1.

			The a(240) = 5 pairs of factorizations::
  (4*4*15)|(4*6*10)
    (6*40)|(15*16)
    (8*30)|(12*20)
   (10*24)|(15*16)
   (12*20)|(15*16)

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from exponents in factorization of n.

Cf. A001055, A285572, A285573, A303362, A303386, A304713, A305149, A305150, A305193, A316476, A317144, A322435, A322436, A322437, A322442, A379958.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
divpropQ[x_,y_]:=And[x!=y,Divisible[x,y]];
Table[Length[Select[Subsets[facs[n],{2}],And[!Or@@divpropQ@@@Tuples[#],!Or@@divpropQ@@@Reverse/@Tuples[#]]&]],{n,100}]

factorizations(n, m=n, f=List([]), z=List([])) = if(1==n, listput(z,Vec(f)); z, my(newf); fordiv(n, d, if((d>1)&&(d<=m), newf = List(f); listput(newf,d); z = factorizations(n/d, d, newf, z))); (z));
is_proper_ndf_pair(fac1,fac2) = { for(i=1,#fac1,for(j=1,#fac2,if((fac1[i]!=fac2[j]) && (!(fac1[i]%fac2[j]) || !(fac2[j]%fac1[i])),return(0)))); (1); };
number_of_proper_ndfpairs(z) = sum(i=1,#z,sum(j=i+1,#z,is_proper_ndf_pair(z[i],z[j])));
A322438(n) = number_of_proper_ndfpairs(Vec(factorizations(n))); \\ Antti Karttunen, Jan 24 2025

Data section extended up to a(144) by Antti Karttunen, Jan 24 2025

A371445 Numbers whose distinct prime indices are binary carry-connected and have no binary containments.

Original entry on oeis.org

2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 55, 59, 61, 64, 65, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 115, 121, 125, 127, 128, 131, 137, 139, 143, 145, 149, 151, 157, 163, 167, 169, 173, 179, 181

Offset: 1

Gus Wiseman, Mar 30 2024

nonn

Also Heinz numbers of binary carry-connected integer partitions whose distinct parts have no binary containments, counted by A371446.
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.
A binary carry of two positive integers is an overlap of binary indices. A multiset is said to be binary carry-connected iff the graph whose vertices are the elements and whose edges are binary carries is connected.
A binary containment is a containment of binary indices. For example, the numbers {3,5} have binary indices {{1,2},{1,3}}, so there is a binary carry but not a binary containment.

			The terms together with their prime indices begin:
     2: {1}            37: {12}              97: {25}
     3: {2}            41: {13}             101: {26}
     4: {1,1}          43: {14}             103: {27}
     5: {3}            47: {15}             107: {28}
     7: {4}            49: {4,4}            109: {29}
     8: {1,1,1}        53: {16}             113: {30}
     9: {2,2}          55: {3,5}            115: {3,9}
    11: {5}            59: {17}             121: {5,5}
    13: {6}            61: {18}             125: {3,3,3}
    16: {1,1,1,1}      64: {1,1,1,1,1,1}    127: {31}
    17: {7}            65: {3,6}            128: {1,1,1,1,1,1,1}
    19: {8}            67: {19}             131: {32}
    23: {9}            71: {20}             137: {33}
    25: {3,3}          73: {21}             139: {34}
    27: {2,2,2}        79: {22}             143: {5,6}
    29: {10}           81: {2,2,2,2}        145: {3,10}
    31: {11}           83: {23}             149: {35}
    32: {1,1,1,1,1}    89: {24}             151: {36}

Contains all powers of primes A000961 except 1.
Case of A325118 (counted by A325098) without binary containments.
For binary indices of binary indices we have A326750 = A326704 /\ A326749.
For prime indices of prime indices we have A329559 = A305078 /\ A316476.
An opposite version is A371294 = A087086 /\ A371291.
Partitions of this type are counted by A371446.
Carry-connected case of A371455 (counted by A325109).
A001187 counts connected graphs.
A007718 counts non-isomorphic connected multiset partitions.
A048143 counts connected antichains of sets.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A070939 gives length of binary expansion.
A326964 counts connected set-systems, covering A323818.
Cf. A019565, A056239, A112798, A304713, A304716, A305079, A305148, A325097, A325105, A325107, A325119, A371452.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Select[Range[100],stableQ[bpe/@prix[#],SubsetQ] && Length[csm[bpe/@prix[#]]]==1&]

Intersection of A371455 and A325118.

A317616 Numbers whose prime multiplicities are not pairwise indivisible.

Original entry on oeis.org

12, 18, 20, 24, 28, 40, 44, 45, 48, 50, 52, 54, 56, 60, 63, 68, 75, 76, 80, 84, 88, 90, 92, 96, 98, 99, 104, 112, 116, 117, 120, 124, 126, 132, 135, 136, 140, 144, 147, 148, 150, 152, 153, 156, 160, 162, 164, 168, 171, 172, 175, 176, 180, 184, 188, 189, 192

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

The numbers of terms that do not exceed 10^k, for k = 2, 3, ..., are 26, 344, 3762, 38711, 390527, 3915874, 39192197, 392025578, 3920580540, ... . Apparently, the asymptotic density of this sequence exists and equals 0.392... . - Amiram Eldar, Sep 25 2024

			72 = 2^3 * 3^2 is not in the sequence because 3 and 2 are pairwise indivisible.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A118914, A124010, A285572, A285573, A303362, A304713, A316475, A317101, A317102.

Select[Range[100],!Select[Tuples[Last/@FactorInteger[#],2],And[UnsameQ@@#,Divisible@@#]&]=={}&]

is(k) = if(k == 1, 0, my(e = Set(factor(k)[,2])); if(vecmax(e) == 1, 0, for(i = 1, #e, for(j = 1, i-1, if(!(e[i] % e[j]), return(1)))); 0)); \\ Amiram Eldar, Sep 25 2024

A318730 Number of cyclic compositions (necklaces of positive integers) summing to n with adjacent parts (including the last and first part) being indivisible (either way).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 3, 6, 5, 8, 7, 14, 15, 21, 31, 39, 51, 69, 98, 133, 177, 254, 329, 471, 632, 902, 1230, 1710, 2370, 3270, 4591, 6384, 8898, 12429, 17252, 24230, 33783, 47405, 66254, 92860, 130142, 182469, 256262, 359676, 505231, 710059, 997953, 1404215

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(14) = 14 cyclic compositions with adjacent parts indivisible either way:
  (14)
  (3,11) (4,10) (5,9) (6,8)
  (2,5,7) (2,7,5) (3,4,7) (3,7,4)
  (2,3,2,7) (2,3,4,5) (2,5,2,5) (2,5,4,3) (3,4,3,4)

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

Cf. A000740, A008965, A059966, A167606, A285573, A303362, A304713, A316476, A318726, A318727, A318728, A318729, A328601.

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

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, 1 + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019

a(n) = A328601(n) + 1. - Andrew Howroyd, Oct 27 2019

Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018

A371446 Number of carry-connected integer partitions whose distinct parts have no binary containments.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 4, 2, 5, 4, 4, 4, 8, 4, 7, 7, 12, 10, 14, 12, 15, 19, 19, 21, 32, 27, 33, 40, 46, 47, 61, 52, 75, 89, 95, 104, 129, 129, 149, 176, 188, 208, 249, 257, 296, 341, 373, 394, 476, 496, 552

Offset: 0

Gus Wiseman, Apr 02 2024

These partitions are ranked by A371445.
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.
A binary carry of two positive integers is an overlap of binary indices. An integer partition is binary carry-connected iff the graph with one vertex for each part and edges corresponding to binary carries is connected.
A binary containment is a containment of binary indices. For example, the numbers {3,5} have binary indices {{1,2},{1,3}}, so there is a binary carry but not a binary containment.

			The a(12) = 8 through a(14) = 7 partitions:
  (12)             (13)                         (14)
  (6,6)            (10,3)                       (7,7)
  (9,3)            (5,5,3)                      (9,5)
  (4,4,4)          (1,1,1,1,1,1,1,1,1,1,1,1,1)  (6,5,3)
  (6,3,3)                                       (5,3,3,3)
  (3,3,3,3)                                     (2,2,2,2,2,2,2)
  (2,2,2,2,2,2)                                 (1,1,1,1,1,1,1,1,1,1,1,1,1,1)
  (1,1,1,1,1,1,1,1,1,1,1,1)

The first condition (carry-connected) is A325098.
The second condition (stable) is A325109.
Ranks for binary indices of binary indices are A326750 = A326704 /\ A326749.
Ranks for prime indices of prime indices are A329559 = A305078 /\ A316476.
Ranks for prime indices of binary indices are A371294 = A087086 /\ A371291.
Ranks for binary indices of prime indices are A371445 = A325118 /\ A371455.
A001187 counts connected graphs.
A007718 counts non-isomorphic connected multiset partitions.
A048143 counts connected antichains of sets.
A048793 lists binary indices, reverse A272020, length A000120, sum A029931.
A070939 gives length of binary expansion.
A326964 counts connected set-systems, covering A323818.
Cf. A019565, A304713, A304716, A305079, A305148, A325097, A325105, A325107, A325119, A371452.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
bix[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n], stableQ[bix/@Union[#],SubsetQ]&&Length[csm[bix/@#]]<=1&]],{n,0,30}]

A319319 Heinz numbers of integer partitions such that every distinct submultiset has a different GCD.

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, 107, 109, 113, 119, 123, 127, 131, 137, 139, 141, 143, 145, 149, 151, 155, 157, 161, 163, 167, 173, 177

Offset: 1

Gus Wiseman, Sep 17 2018

nonn

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

First differs from A304713 (Heinz numbers of pairwise indivisible partitions) at A304713(58) = 165, which is absent from this sequence because its prime indices are {2,3,5} and GCD(2,3) = GCD(2,3,5) = 1. The first term with more than two prime factors is 17719, which has prime indices {6,10,15}. The first term with more than two prime factors that is absent from A318716 is 296851, which has prime indices {12,20,30}.

			The sequence of partitions whose Heinz numbers are in the sequence begins: (), (1), (2), (3), (4), (5), (6), (3,2), (7), (8), (9), (10), (11), (5,2), (4,3), (12), (13), (14), (15), (7,2), (16), (5,3).

Cf. A056239, A108917, A122768, A275972, A299702, A301899, A301900, A304713, A316313, A319315, A319318, A319327.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],UnsameQ@@GCD@@@Union[Subsets[primeMS[#]]]&]

A319327 Heinz numbers of integer partitions such that every distinct submultiset has a different LCM.

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, 107, 109, 113, 119, 123, 127, 131, 137, 139, 141, 143, 145, 149, 151, 155, 157, 161, 163, 165, 167, 173

Offset: 1

Gus Wiseman, Sep 17 2018

nonn

Note that such a Heinz number is necessarily squarefree, as such a partition is necessarily strict.
The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
First differs from A304713 (Heinz numbers of pairwise indivisible partitions) at A304713(642) = 2093, which is absent from this sequence because its prime indices are {4,6,9} and LCM(4,9) = LCM(4,6,9) = 36.

			The sequence of partitions whose Heinz numbers are in the sequence begins: (), (1), (2), (3), (4), (5), (6), (3,2), (7), (8), (9), (10), (11), (5,2), (4,3), (12), (13), (14), (15), (7,2).

Cf. A056239, A108917, A122768, A275972, A299702, A301899, A301900, A304713, A316313, A319315, A319319, A319320.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],UnsameQ@@LCM@@@Union[Subsets[primeMS[#]]]&]

A338330 Numbers that are neither a power of a prime (A000961) nor is their set of distinct prime indices pairwise coprime.

Original entry on oeis.org

21, 39, 42, 57, 63, 65, 78, 84, 87, 91, 105, 111, 114, 115, 117, 126, 129, 130, 133, 147, 156, 159, 168, 171, 174, 182, 183, 185, 189, 195, 203, 210, 213, 222, 228, 230, 231, 234, 235, 237, 247, 252, 258, 259, 260, 261, 266, 267, 273, 285, 294, 299, 301

Offset: 1

Gus Wiseman, Nov 12 2020

nonn

Also Heinz numbers of partitions that are neither constant (A144300) nor have pairwise coprime distinct parts (A304709), hence the formula. The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

			The sequence of terms together with their prime indices begins:
     21: {2,4}        126: {1,2,2,4}      203: {4,10}
     39: {2,6}        129: {2,14}         210: {1,2,3,4}
     42: {1,2,4}      130: {1,3,6}        213: {2,20}
     57: {2,8}        133: {4,8}          222: {1,2,12}
     63: {2,2,4}      147: {2,4,4}        228: {1,1,2,8}
     65: {3,6}        156: {1,1,2,6}      230: {1,3,9}
     78: {1,2,6}      159: {2,16}         231: {2,4,5}
     84: {1,1,2,4}    168: {1,1,1,2,4}    234: {1,2,2,6}
     87: {2,10}       171: {2,2,8}        235: {3,15}
     91: {4,6}        174: {1,2,10}       237: {2,22}
    105: {2,3,4}      182: {1,4,6}        247: {6,8}
    111: {2,12}       183: {2,18}         252: {1,1,2,2,4}
    114: {1,2,8}      185: {3,12}         258: {1,2,14}
    115: {3,9}        189: {2,2,2,4}      259: {4,12}
    117: {2,2,6}      195: {2,3,6}        260: {1,1,3,6}

A338331 is the complement.
A304713 is the complement of the version for divisibility.
Cf. A056239, A112798, A289509, A303282, A316476, A318716, A318719, A328867.

Select[Range[2,100],!PrimePowerQ[#]&&!CoprimeQ@@Union[PrimePi/@First/@FactorInteger[#]]&]

Equals A024619 \ A304711.

A371455 Numbers k such that if we take the binary indices of each prime index of k we get an antichain of sets.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 35, 36, 37, 38, 41, 42, 43, 47, 48, 49, 52, 53, 54, 55, 56, 57, 58, 59, 61, 63, 64, 65, 67, 69, 71, 72, 73, 74, 76, 79, 81, 83, 84, 86, 89, 95, 96, 97, 98, 99

Offset: 1

Gus Wiseman, Apr 01 2024

nonn

In an antichain of sets, no edge is a proper subset of any other.

			The prime indices of 65 are {3,6} with binary indices {{1,2},{2,3}} so 65 is in the sequence.
The prime indices of 255 are {2,3,7} with binary indices {{2},{1,2},{1,2,3}} so 255 is not in the sequence.

Jakub Buczak, Table of n, a(n) for n = 1..10000

Contains all powers of primes A000961.
An opposite version is A087086, carry-connected case A371294.
For prime indices of prime indices we have A316476, carry-connected A329559.
These antichains are counted by A325109.
For binary indices of binary indices we have A326704, carry-conn. A326750.
The carry-connected case is A371445, counted by A371446.
A048143 counts connected antichains of sets.
A048793 lists binary indices, reverse A272020, length A000120, sum A029931.
A050320 counts set multipartitions of prime indices, see also A318360.
A070939 gives length of binary expansion.
A089259 counts set multipartitions of integer partitions.
A112798 lists prime indices, reverse A296150, length A001222, sum A056239.
A116540 counts normal set multipartitions.
A302478 ranks set multipartitions, cf. A073576.
A325118 ranks carry-connected partitions, counted by A325098.
A371451 counts carry-connected components of binary indices.
Cf. A019565, A050326, A304713, A305148, A325097, A325107, A371291, A371452.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
bix[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],stableQ[bix/@prix[#],SubsetQ]&]

A317101 Numbers whose prime multiplicities are pairwise indivisible.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 64, 65, 66, 67, 69, 70, 71, 72, 73, 74, 77, 78, 79, 81, 82, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

			72 = 2^3 * 3^2 is in the sequence because 3 and 2 are pairwise indivisible.

Cf. A118914, A124010, A285572, A285573, A303362, A304713, A316475, A317102, A317616.

Select[Range[100],Select[Tuples[Last/@FactorInteger[#],2],And[UnsameQ@@#,Divisible@@#]&]=={}&]

cp's OEIS Frontend

A322438 Number of unordered pairs of factorizations of n into factors > 1 where no factor of one properly divides any factor of the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A371445 Numbers whose distinct prime indices are binary carry-connected and have no binary containments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A317616 Numbers whose prime multiplicities are not pairwise indivisible.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A318730 Number of cyclic compositions (necklaces of positive integers) summing to n with adjacent parts (including the last and first part) being indivisible (either way).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A371446 Number of carry-connected integer partitions whose distinct parts have no binary containments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A319319 Heinz numbers of integer partitions such that every distinct submultiset has a different GCD.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A319327 Heinz numbers of integer partitions such that every distinct submultiset has a different LCM.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A338330 Numbers that are neither a power of a prime (A000961) nor is their set of distinct prime indices pairwise coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs