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,2

Links

Sebastian Karlsson, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Prime Factor

Formula

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

Example

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A001222, A319169, A339512, A339514.

Sequence in context: A347443 A329235 A241829 * A250179 A202823 A013931

Adjacent sequences: A339508 A339509 A339510 * A339512 A339513 A339514

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 07 2020

Extensions

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

Status

approved