login
A339512
Number of subsets of {1..n} whose elements have the same number of distinct prime factors.
3
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
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
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, Dec 07 2020
EXTENSIONS
a(23)-a(42) from Michael S. Branicky, Dec 07 2020
STATUS
approved