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
Keywords
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
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