A084422 -id:A084422 - cp's OEIS frontend

A007360 Number of partitions of n into distinct and pairwise relatively prime parts.

1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 8, 9, 10, 11, 10, 13, 17, 19, 21, 22, 21, 24, 32, 37, 37, 38, 40, 45, 55, 65, 69, 66, 64, 75, 86, 100, 113, 107, 106, 122, 145, 165, 174, 167, 162, 179, 222, 253, 255, 255, 255, 273, 328, 373, 376, 369, 377, 406, 476, 553, 569, 537, 529

Offset: 1

N. J. A. Sloane and Mira Bernstein, following a suggestion from Marc LeBrun

			From _Gus Wiseman_, Sep 23 2019: (Start)
The a(1) = 1 through a(10) = 6 partitions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)    (7)   (8)    (9)    (A)
            (21)  (31)  (32)  (51)   (43)  (53)   (54)   (73)
                        (41)  (321)  (52)  (71)   (72)   (91)
                                     (61)  (431)  (81)   (532)
                                           (521)  (531)  (541)
                                                         (721)
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..750 (terms 1..350 from Alois P. Heinz)
M. LeBrun & D. Hoey, Emails

Number of partitions of n into relatively prime parts = A000837.
The non-strict case is A051424.
Strict relatively prime partitions are A078374.
Cf. A007359, A038348, A084422, A186974, A187106, A303140, A302569, A303362, A304714, A320426, A320436.

$RecursionLimit = 1000; b[n_, i_, s_] := b[n, i, s] = Module[{f}, If[n == 0 || i == 1, 1, If[i<2, 0, f = FactorInteger[i][[All, 1]]; b[n, i-1, Select[s, #Jean-François Alcover, Mar 20 2014, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n],Length[#]==1||UnsameQ@@#&&CoprimeQ@@Union[#]&]],{n,0,30}] (* Gus Wiseman, Sep 23 2019 *)

a(n) = A051424(n)-A051424(n-2). - Vladeta Jovovic, Dec 11 2004

More precise definition from Vladeta Jovovic, Dec 11 2004

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005

A087087 Coprime sets of integers, each subset mapped onto a unique binary integer, values here shown in decimal.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 28, 29, 32, 33, 48, 49, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 76, 77, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 92, 93, 96, 97, 112, 113, 128, 129, 132, 133, 144, 145, 148, 149, 192, 193, 196, 197

Offset: 0

Alan Sutcliffe (alansut(AT)ntlworld.com), Aug 16 2003

A coprime set of integers has no pair of elements for which (i,j)=0. 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 non-coprime subsets.

			a(11)=13 since the 11th coprime set counting from 0 is {4,3,1}, which maps onto 1101 binary = 13 decimal.

Alan Sutcliffe, Divisors and Common Factors in Sets of Integers, awaiting publication.

Ivan Neretin, Table of n, a(n) for n = 0..3232 (all terms up to 2^20)

A087086 gives the corresponding values for the primitive sets of integers. A084422 gives the number of coprime subsets of the integers 1 to n.

a = {}; Do[set = Select[Range[Log2[n] + 1], Reverse[IntegerDigits[n, 2]][[#]] == 1 &]; If[Union@Flatten@Outer[If[#1 == #2, 1, GCD[#1, #2]] &, set, set] == {1}, AppendTo[a, n]], {n, 200}]; a (* Ivan Neretin, Aug 14 2015 *)

A062319 Number of divisors of n^n, or of A000312(n).

Original entry on oeis.org

1, 1, 3, 4, 9, 6, 49, 8, 25, 19, 121, 12, 325, 14, 225, 256, 65, 18, 703, 20, 861, 484, 529, 24, 1825, 51, 729, 82, 1653, 30, 29791, 32, 161, 1156, 1225, 1296, 5329, 38, 1521, 1600, 4961, 42, 79507, 44, 4005, 4186, 2209, 48, 9457, 99, 5151, 2704, 5565, 54

Offset: 0

Jason Earls, Jul 05 2001

From Gus Wiseman, May 02 2021: (Start)
Conjecture: The number of divisors of n^n equals the number of pairwise coprime ordered n-tuples of divisors of n. Confirmed up to n = 30. For example, the a(1) = 1 through a(5) = 6 tuples are:
  (1)  (1,1)  (1,1,1)  (1,1,1,1)  (1,1,1,1,1)
       (1,2)  (1,1,3)  (1,1,1,2)  (1,1,1,1,5)
       (2,1)  (1,3,1)  (1,1,1,4)  (1,1,1,5,1)
              (3,1,1)  (1,1,2,1)  (1,1,5,1,1)
                       (1,1,4,1)  (1,5,1,1,1)
                       (1,2,1,1)  (5,1,1,1,1)
                       (1,4,1,1)
                       (2,1,1,1)
                       (4,1,1,1)
The unordered case (pairwise coprime n-multisets of divisors of n) is counted by A343654.
(End)

			From _Gus Wiseman_, May 02 2021: (Start)
The a(1) = 1 through a(5) = 6 divisors:
  1  1  1   1    1
     2  3   2    5
     4  9   4    25
        27  8    125
            16   625
            32   3125
            64
            128
            256
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from Harry J. Smith)

Cf. A046798, A077592, A035116. - Enrique Pérez Herrero, Nov 09 2010
Number of divisors of A000312(n).
Taking Omega instead of sigma gives A066959.
Positions of squares are A173339.
Diagonal n = k of the array A343656.
A000005 counts divisors.
A059481 counts k-multisets of elements of {1..n}.
A334997 counts length-k strict chains of divisors of n.
A343658 counts k-multisets of divisors.
Pairwise coprimality:
- A018892 counts coprime pairs of divisors.
- A084422 counts pairwise coprime subsets of {1..n}.
- A100565 counts pairwise coprime triples of divisors.
- A225520 counts pairwise coprime sets of divisors.
- A343652 counts maximal pairwise coprime sets of divisors.
- A343653 counts pairwise coprime non-singleton sets of divisors > 1.
- A343654 counts pairwise coprime sets of divisors > 1.
Cf. A000169, A000272, A002064, A002109, A009998, A048691, A143773, A146291, A176029, A327527, A343657.

[NumberOfDivisors(n^n): n in  [0..60]]; // Vincenzo Librandi, Nov 09 2014

A062319[n_IntegerQ]:=DivisorSigma[0,n^n]; (* Enrique Pérez Herrero, Nov 09 2010 *)
Join[{1},DivisorSigma[0,#^#]&/@Range[60]] (* Harvey P. Dale, Jun 06 2024 *)

je=[]; for(n=0,200,je=concat(je,numdiv(n^n))); je

{ for (n=0, 1000, write("b062319.txt", n, " ", numdiv(n^n)); ) } \\ Harry J. Smith, Aug 04 2009

a(n)=local(fm);fm=factor(n);prod(k=1,matsize(fm)[1],fm[k,2]*n+1) \\ Franklin T. Adams-Watters, May 03 2011

a(n) = if(n==0, 1, sumdiv(n, d, n^omega(d))); \\ Seiichi Manyama, May 12 2021

from math import prod
from sympy import factorint
def A062319(n): return prod(n*d+1 for d in factorint(n).values()) # Chai Wah Wu, Jun 03 2021

a(n) = A000005(A000312(n)). - Enrique Pérez Herrero, Nov 09 2010
a(2^n) = A002064(n). - Gus Wiseman, May 02 2021
a(prime(n)) = prime(n) + 1. - Gus Wiseman, May 02 2021
a(n) = Product_{i=1..s} (1 + n * m_i) where (m_1,...,m_s) is the sequence of prime multiplicities (prime signature) of n. - Gus Wiseman, May 02 2021
a(n) = Sum_{d|n} n^omega(d) for n > 0. - Seiichi Manyama May 12 2021

A324736 Number of subsets of {1...n} containing all prime indices of the elements.

Original entry on oeis.org

1, 2, 3, 4, 7, 9, 15, 22, 43, 79, 127, 175, 343, 511, 851, 1571, 3141, 4397, 8765, 13147, 25243, 46843, 76795, 115171, 230299, 454939, 758203, 1516363, 2916079, 4356079, 8676079, 12132079, 24264157, 45000157, 73800253, 145685053, 291369853, 437054653, 728424421

Offset: 0

Gus Wiseman, Mar 13 2019

nonn

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 the number of subsets of {1...n} containing no prime indices of the non-elements up to n.

			The a(0) = 1 through a(6) = 15 subsets:
  {}  {}   {}     {}       {}         {}           {}
      {1}  {1}    {1}      {1}        {1}          {1}
           {1,2}  {1,2}    {1,2}      {1,2}        {1,2}
                  {1,2,3}  {1,4}      {1,4}        {1,4}
                           {1,2,3}    {1,2,3}      {1,2,3}
                           {1,2,4}    {1,2,4}      {1,2,4}
                           {1,2,3,4}  {1,2,3,4}    {1,2,6}
                                      {1,2,3,5}    {1,2,3,4}
                                      {1,2,3,4,5}  {1,2,3,5}
                                                   {1,2,3,6}
                                                   {1,2,4,6}
                                                   {1,2,3,4,5}
                                                   {1,2,3,4,6}
                                                   {1,2,3,5,6}
                                                   {1,2,3,4,5,6}
An example for n = 18 is {1,2,4,7,8,9,12,16,17,18}, whose elements have the following prime indices:
   1: {}
   2: {1}
   4: {1,1}
   7: {4}
   8: {1,1,1}
   9: {2,2}
  12: {1,1,2}
  16: {1,1,1,1}
  17: {7}
  18: {1,2,2}
All of these prime indices {1,2,4,7} belong to the subset, as required.

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

The strict integer partition version is A324748. The integer partition version is A324753. The Heinz number version is A290822. An infinite version is A324698.
Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A279861, A290689, A304360, A320426.
Cf. A324697, A324737, A324741, A324743.

Table[Length[Select[Subsets[Range[n]],SubsetQ[#,PrimePi/@First/@Join@@FactorInteger/@DeleteCases[#,1]]&]],{n,0,10}]

pset(n)={my(b=0, f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 15 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 15 2019

A324741 Number of subsets of {1...n} containing no prime indices of the elements.

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 19, 30, 54, 96, 156, 248, 440, 688, 1120, 1864, 3664, 5856, 11232, 16896, 31296, 53952, 91008, 137472, 270528, 516720, 863088, 1710816, 3173856, 4836672, 9329472, 14897376, 29788128, 52256448, 88429248, 166037184, 331648704, 497685888, 829449600

Offset: 0

Gus Wiseman, Mar 15 2019

nonn

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 a(0) = 1 through a(6) = 19 subsets:
  {}  {}   {}   {}     {}     {}       {}
      {1}  {1}  {1}    {1}    {1}      {1}
           {2}  {2}    {2}    {2}      {2}
                {3}    {3}    {3}      {3}
                {1,3}  {4}    {4}      {4}
                       {1,3}  {5}      {5}
                       {2,4}  {1,3}    {6}
                       {3,4}  {1,5}    {1,3}
                              {2,4}    {1,5}
                              {2,5}    {2,4}
                              {3,4}    {2,5}
                              {4,5}    {3,4}
                              {2,4,5}  {3,6}
                                       {4,5}
                                       {4,6}
                                       {5,6}
                                       {2,4,5}
                                       {3,4,6}
                                       {4,5,6}
An example for n = 20 is {5,6,7,9,10,12,14,15,16,19,20}, with prime indices:
   5: {3}
   6: {1,2}
   7: {4}
   9: {2,2}
  10: {1,3}
  12: {1,1,2}
  14: {1,4}
  15: {2,3}
  16: {1,1,1,1}
  19: {8}
  20: {1,1,3}
None of these prime indices {1,2,3,4,8} belong to the subset, as required.

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

The maximal case is A324743. The strict integer partition version is A324751. The integer partition version is A324756. The Heinz number version is A324758. An infinite version is A304360.
Cf. A000720, A001462, A007097, A076078, A084422, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
Cf. A324695, A324736, A324742.

Table[Length[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,0,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitand(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

A324743 Number of maximal subsets of {1...n} containing no prime indices of the elements.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 8, 8, 8, 8, 12, 12, 18, 18, 19, 19, 30, 30, 54, 54, 54, 54, 96, 96, 96, 96, 96, 96, 156, 156, 244, 244, 248, 248, 248, 248, 440, 440, 440, 440, 688, 688, 1120, 1120, 1120, 1120, 1864, 1864, 1864, 1864, 1864, 1864, 3664, 3664, 3664, 3664, 3664

Offset: 0

Gus Wiseman, Mar 15 2019

nonn

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 a(0) = 1 through a(8) = 8 maximal subsets:
  {}  {1}  {1}  {2}    {1,3}  {1,3}    {1,3}    {1,3,7}  {1,3,7}
           {2}  {1,3}  {2,4}  {1,5}    {1,5}    {1,5,7}  {1,5,7}
                       {3,4}  {3,4}    {2,4,5}  {2,4,5}  {2,4,5,8}
                              {2,4,5}  {3,4,6}  {2,5,7}  {2,5,7,8}
                                       {4,5,6}  {3,4,6}  {3,4,6,8}
                                                {3,6,7}  {3,6,7,8}
                                                {4,5,6}  {4,5,6,8}
                                                {5,6,7}  {5,6,7,8}
An example for n = 15 is {1,5,7,9,13,15}, with prime indices:
  1: {}
  5: {3}
  7: {4}
  9: {2,2}
  13: {6}
  15: {2,3}
None of these prime indices {2,3,4,6} belong to the subset, as required.

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

The non-maximal case is A324741. The case for subsets of {2...n} is A324763.
Cf. A000720, A001462, A007097, A084422, A085945, A112798, A276625, A290689, A290822, A304360, A306844, A320426, A324764.
Cf. A324695, A324736, A324742, A324744, A324751, A324756, A324758.

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]]],{n,0,10}]

pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n, k, pset(k)), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=my(e=0); forstep(k=#p, 1, -1, if(bittest(b,k), e=bitor(e,p[k]), if(!bittest(e,k) && !bitand(p[k], b), return(0)) )); 1);
((k, b)->if(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 26 2019

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

A187106 Number of nonempty subsets of {1, 2, ..., n} having pairwise coprime elements.

Original entry on oeis.org

1, 3, 7, 11, 23, 27, 55, 71, 103, 115, 231, 247, 495, 543, 615, 727, 1455, 1519, 3039, 3231, 3615, 3871, 7743, 7999, 11167, 11903, 14655, 15487, 30975, 31231, 62463, 69887, 76159, 80255, 89855, 91647, 183295, 192639, 208639, 214271, 428543

Offset: 1

Alois P. Heinz, Mar 06 2011

nonn

			a(4) = 11 because there are 11 nonempty subsets of {1,2,3,4} having pairwise coprime elements: {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}.

Alois P. Heinz, Table of n, a(n) for n = 1..220

Cf. A036234. Row sums of triangle A186974. Partial sums of A186973. Rightmost elements in rows of triangle A187262.

Cf. A084422.

f(n,k=1)=if(n==1, return(2)); if(gcd(k,n)==1, f(n-1,n*k)) + f(n-1,k)
a(n)=f(n)-1 \\ Charles R Greathouse IV, Aug 24 2016

a(n) = Sum_{k=1..A036234(n)} A186974(n,k).
a(n) = Sum_{i=1..n} A186973(i).
a(n) = A187262(n,A036234(n)).
a(n) = A084422(n) - 1.

A320426 Number of nonempty pairwise coprime subsets of {1,...,n}, where a single number is not considered to be pairwise coprime unless it is equal to 1.

Original entry on oeis.org

1, 2, 5, 8, 19, 22, 49, 64, 95, 106, 221, 236, 483, 530, 601, 712, 1439, 1502, 3021, 3212, 3595, 3850, 7721, 7976, 11143, 11878, 14629, 15460, 30947, 31202, 62433, 69856, 76127, 80222, 89821, 91612, 183259, 192602, 208601, 214232, 428503, 431574, 863189

Offset: 1

Gus Wiseman, Jan 08 2019

nonn

Two or more numbers are pairwise coprime if no pair of them has a common divisor > 1.

			The a(4) = 8 subsets of {1,2,3,4} are {1}, {1,2}, {1,3}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,3,4}. - _Michael B. Porter_, Jan 12 2019
From _Gus Wiseman_, May 09 2021: (Start)
The a(2) = 2 through a(6) = 22 sets:
   {1}     {1}      {1}       {1}        {1}
  {1,2}   {1,2}    {1,2}     {1,2}      {1,2}
          {1,3}    {1,3}     {1,3}      {1,3}
          {2,3}    {1,4}     {1,4}      {1,4}
         {1,2,3}   {2,3}     {1,5}      {1,5}
                   {3,4}     {2,3}      {1,6}
                  {1,2,3}    {2,5}      {2,3}
                  {1,3,4}    {3,4}      {2,5}
                             {3,5}      {3,4}
                             {4,5}      {3,5}
                            {1,2,3}     {4,5}
                            {1,2,5}     {5,6}
                            {1,3,4}    {1,2,3}
                            {1,3,5}    {1,2,5}
                            {1,4,5}    {1,3,4}
                            {2,3,5}    {1,3,5}
                            {3,4,5}    {1,4,5}
                           {1,2,3,5}   {1,5,6}
                           {1,3,4,5}   {2,3,5}
                                       {3,4,5}
                                      {1,2,3,5}
                                      {1,3,4,5}
(End)

The case of pairs is A015614.
The case with singletons is A187106.
The version without singletons (except {1}) is A276187.
Row sums of A320436.
The version for divisors > 1 is A343654.
The version for divisors without singletons is A343655.
The maximal version is A343659.
A018892 counts coprime unordered pairs of divisors.
A051026 counts pairwise indivisible subsets of {1...n}.
A087087 ranks pairwise coprime subsets of {1...n}.
A326675 ranks pairwise coprime non-singleton subsets of {1...n}.
Cf. A007359, A007360, A066620, A089233, A100565, A225520, A325683, A326359, A337485, A343652.

Table[Length[Select[Subsets[Range[n]],CoprimeQ@@#&]],{n,10}]

a(n) = A187106(n) - n + 1 = A084422(n) - n.

a(n) = A276187(n) + 1. - Gus Wiseman, May 08 2021

a(25)-a(43) from Alois P. Heinz, Jan 08 2019

A324744 Number of maximal subsets of {1...n} containing no element whose prime indices all belong to the subset.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 11, 11, 22, 22, 22, 22, 28, 28, 44, 44, 52, 52, 76, 76, 88, 88, 96, 96, 184, 184, 240, 240, 264, 264, 296, 296, 592, 592, 592, 592, 728, 728, 1456, 1456, 1456, 1456, 2912, 2912, 3168, 3168, 3168, 3168, 5568, 5568, 5568, 5568

Offset: 0

Gus Wiseman, Mar 15 2019

nonn

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 a(1) = 1 through a(8) = 6 maximal subsets:
  {1}  {1}  {2}    {1,3}  {1,3}    {1,3,6}    {3,4,6}    {1,3,6,7}
       {2}  {1,3}  {2,4}  {1,5}    {1,5,6}    {1,3,6,7}  {1,5,6,7}
                   {3,4}  {3,4}    {3,4,6}    {1,5,6,7}  {3,4,6,8}
                          {2,4,5}  {2,4,5,6}  {2,4,5,6}  {3,6,7,8}
                                              {2,5,6,7}  {2,4,5,6,8}
                                                         {2,5,6,7,8}

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

The non-maximal case is A324738. The case for subsets of {2...n} is A324762.
Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290822, A304360, A306844, A320426, A324764.
Cf. A324694, A324736, A324743, A324749, A324754, A324759.

maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];
Table[Length[maxim[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]]],{n,0,10}]

pset(n)={my(b=0, f=factor(n)[, 1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n, k, if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
my(ismax(b)=for(k=1, #p, if(!bittest(b,k) && bitnegimply(p[k], b), my(e=bitor(b, 1<#p, ismax(b), my(f=bitnegimply(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 27 2019

Terms a(16) and beyond from Andrew Howroyd, Aug 27 2019

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 26, 42, 72, 120, 232, 376, 752, 1128, 2256, 4512, 8256, 13632, 27264, 42048, 82944, 158976, 313344, 497664, 995328, 1700352, 3350016, 5815296, 11630592, 17491968, 34983936, 56954880, 108933120, 210788352, 418258944, 804667392, 1609334784

Offset: 0

Gus Wiseman, Mar 13 2019

nonn

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 a(0) = 1 through a(6) = 26 subsets:
  {}  {}   {}   {}     {}     {}       {}
      {1}  {1}  {1}    {1}    {1}      {1}
           {2}  {2}    {2}    {2}      {2}
                {3}    {3}    {3}      {3}
                {1,3}  {4}    {4}      {4}
                       {1,3}  {5}      {5}
                       {2,4}  {1,3}    {6}
                       {3,4}  {1,5}    {1,3}
                              {2,4}    {1,5}
                              {2,5}    {1,6}
                              {3,4}    {2,4}
                              {4,5}    {2,5}
                              {2,4,5}  {2,6}
                                       {3,4}
                                       {3,6}
                                       {4,5}
                                       {4,6}
                                       {5,6}
                                       {1,3,6}
                                       {1,5,6}
                                       {2,4,5}
                                       {2,4,6}
                                       {2,5,6}
                                       {3,4,6}
                                       {4,5,6}
                                       {2,4,5,6}

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

The maximal case is A324744. The case of subsets of {2...n} is A324739. The strict integer partition version is A324749. The integer partition version is A324754. The Heinz number version is A324759. An infinite version is A324694.
Cf. A000720, A001221, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
Cf. A324695, A324736, A324741, A324750, A324755, A324760.

Table[Length[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,0,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

cp's OEIS Frontend

A007360 Number of partitions of n into distinct and pairwise relatively prime parts.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A087087 Coprime sets of integers, each subset mapped onto a unique binary integer, values here shown in decimal.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A062319 Number of divisors of n^n, or of A000312(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

A324736 Number of subsets of {1...n} containing all prime indices of the elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324741 Number of subsets of {1...n} containing no prime indices of the elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324743 Number of maximal subsets of {1...n} containing no prime indices of the elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A187106 Number of nonempty subsets of {1, 2, ..., n} having pairwise coprime elements.

Views

Author