A370585 Number of maximal subsets of {1..n} such that it is possible to choose a different prime factor of each element.

1, 1, 1, 1, 2, 2, 5, 5, 7, 11, 25, 25, 38, 38, 84, 150, 178, 178, 235, 235, 341, 579, 1235, 1235, 1523, 1968, 4160, 4824, 6840, 6840, 9140, 9140, 10028, 16264, 33956, 48680, 56000, 56000, 116472, 186724, 223884, 223884, 290312, 290312, 403484, 484028, 1001420

Offset: 0

Author

Gus Wiseman, Feb 26 2024

Keywords

• nonn

Comments

First differs from A307984 at a(21) = 579, A307984(21) = 578. The difference is due to the set {10,11,13,14,15,17,19,21}, which is not a basis because log(10) + log(21) = log(14) + log(15).

Also length-pi(n) subsets of {1..n} such that it is possible to choose a different prime factor of each element.

Examples

			The a(0) = 1 through a(8) = 7 subsets:
  {}  {}  {2}  {2,3}  {2,3}  {2,3,5}  {2,3,5}  {2,3,5,7}  {2,3,5,7}
                      {3,4}  {3,4,5}  {2,5,6}  {2,5,6,7}  {2,5,6,7}
                                      {3,4,5}  {3,4,5,7}  {3,4,5,7}
                                      {3,5,6}  {3,5,6,7}  {3,5,6,7}
                                      {4,5,6}  {4,5,6,7}  {3,5,7,8}
                                                          {4,5,6,7}
                                                          {5,6,7,8}
		

Crossrefs

Multisets of this type are ranked by A368100, complement A355529.

Factorizations of this type are counted by A368414, complement A368413.

The version for set-systems is A368601, max of A367902 (complement A367903).

This is the maximal case of A370582, complement A370583, cf. A370584.

A different kind of maximality is A370586, complement A370587.

The case containing n is A370590, complement A370591.

Partitions of this type (choosable) are A370592, complement A370593.

For binary indices instead of factors we have A370640, cf. A370636, A370637.

A006530 gives greatest prime factor, least A020639.

A027746 lists prime factors, A112798 indices, length A001222.

A307984 counts Q-bases of logarithms of positive integers.

A355741 counts choices of a prime factor of each prime index.

Cf. A000040, A000720, A005117, A045778, A133686, A333331, A355739, A355740, A355744, A355745, A367905, A368110.

Programs

Mathematica

Table[Length[Select[Subsets[Range[n], {PrimePi[n]}],Length[Select[Tuples[If[#==1, {},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]],{n,0,10}]

Extensions

More terms from Jinyuan Wang, Feb 14 2025