A339514 Number of subsets of {1..n} whose elements have the same number of divisors.

1, 2, 3, 5, 6, 10, 11, 19, 21, 23, 27, 43, 44, 76, 84, 100, 101, 165, 167, 295, 299, 331, 395, 651, 652, 656, 784, 1040, 1048, 1560, 1562, 2586, 2602, 3114, 4138, 6186, 6187, 8235, 12331, 20523, 20527, 24623, 24631, 32823, 32855, 32919, 49303, 65687, 65688

Offset: 0

Author

Ilya Gutkovskiy, Dec 07 2020

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Cf. A000005, A339511, A339512, A047983.

Programs

Python

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

Formula

a(0) = 1, a(n) = a(n-1) + 2^A047983(n). - Sebastian Karlsson, Dec 26 2020

Extensions

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