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

Links

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

Eric Weisstein's World of Mathematics, Distinct Prime Factors

Formula

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

Example

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}.

Prog

(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

Crossrefs

Cf. A001221, A339511, A339514.

Sequence in context: A352944 A154223 A061031 * A326023 A326117 A319380

Adjacent sequences: A339509 A339510 A339511 * A339513 A339514 A339515

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 07 2020

Extensions

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

Status

approved