A339512 Number of subsets of {1..n} whose elements have the same number of distinct prime factors.

1, 2, 3, 5, 9, 17, 18, 34, 66, 130, 132, 260, 264, 520, 528, 544, 1056, 2080, 2112, 4160, 4224, 4352, 4608, 8704, 9216, 17408, 18432, 34816, 36864, 69632, 69633, 135169, 266241, 270337, 278529, 294913, 327681, 589825, 655361, 786433, 1048577, 1572865, 1572867

Offset: 0

Author

Ilya Gutkovskiy, Dec 07 2020

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A001221, A339511, A339514.

Programs

Python

from sympy import primefactors
def test(n):
    if n==0: return -1
    return len(primefactors(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(43)]) # Michael S. Branicky, Dec 07 2020

Formula

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

Extensions

a(23)-a(42) from Michael S. Branicky, Dec 07 2020