A339511 Number of subsets of {1..n} whose elements have the same number of prime factors, counted with multiplicity.

1, 2, 3, 5, 6, 10, 12, 20, 21, 25, 33, 49, 51, 83, 99, 131, 132, 196, 200, 328, 336, 400, 528, 784, 786, 1042, 1554, 1570, 1602, 2114, 2178, 3202, 3203, 4227, 6275, 10371, 10375, 12423, 20615, 36999, 37007, 41103, 41231, 49423, 49679, 50191, 82959, 99343, 99345, 164881, 165905, 296977, 299025, 331793, 331809, 593953, 593985, 1118273, 2166849, 2232385

Offset: 0

Author

Ilya Gutkovskiy, Dec 07 2020

Keywords

• nonn

Examples

			a(6) = 12 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {2, 3}, {2, 5}, {3, 5}, {4, 6} and {2, 3, 5}.
		

Links

• Sebastian Karlsson, Table of n, a(n) for n = 0..10000
• Eric Weisstein's World of Mathematics, Prime Factor

Crossrefs

Cf. A001222, A319169, A339512, A339514.

Programs

Mathematica

Array[Count[Subsets@ Range[#], ?(SameQ @@ PrimeOmega[#] &)] &, 16, 0] (* _Michael De Vlieger, Feb 24 2021 *)

Python

from sympy import primeomega
def test(n):
    if n<2: return n-1
    return primeomega(n)
def a(n):
    tests = [test(i) for i in range(n+1)]
    return sum(2**tests.count(v)-1 for v in set(tests))
print([a(n) for n in range(60)]) # Michael S. Branicky, Dec 07 2020

Formula

a(n) = 1 + Sum_{k=1..n} 2^A335097(k). - Sebastian Karlsson, Feb 23 2021

Extensions

a(25)-a(48) from Michael S. Branicky, Dec 07 2020