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

Links

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

Eric Weisstein's World of Mathematics, Divisor

Formula

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

Example

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

Prog

(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

Crossrefs

Cf. A000005, A339511, A339512, A047983.

Sequence in context: A302600 A053436 A057546 * A138587 A099350 A337218

Adjacent sequences: A339511 A339512 A339513 * A339515 A339516 A339517

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 07 2020

Extensions

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

Status

approved