A384330 Number of distinct subsets S of [n] such that for all 1 <= k <= n, there exist elements x,y in S (not necessarily distinct) such that x*y = 2k.

1, 0, 1, 1, 1, 1, 3, 3, 8, 11, 30, 30, 57, 57, 159, 295, 427, 427, 1033, 1033, 1973, 3610, 10427, 10427, 20575, 28731, 83535, 142793, 273755, 273755, 549946, 549946, 1245416, 2289562, 6665252, 12386159, 24210731, 24210731, 71150197, 131657471, 256115337, 256115337

Offset

0,7

Links

Table of n, a(n) for n=0..41.

Formula

a(p) = a(p-1) for odd prime p. - Jinyuan Wang, May 26 2025

Example

a(6) = 3 because there are three sets that match the said condition: {1,2,3,4,5}, {1,2,4,5,6} and {1,2,3,4,5,6}.

Prog

(Python)
def a(n):
    if n == 0: return 1
    t = set(k << 1 for k in range(1, n+1))
    c = 0
    for i in range(1, (1 << n)+1, 2):
        s = [j+1 for j in range(n) if (i >> j) & 1]
        if len(s) == 0 or s[0] != 1: continue
        ss = set(x * y for x in s for y in s if not (x & 1 and y & 1) )
        if t.issubset(ss): c += 1
    return c
print([a(n) for n in range(0, 29)])

Crossrefs

Cf. A000079, A000225, A383968.

Sequence in context: A381936 A105039 A358834 * A346005 A276552 A213030

Adjacent sequences: A384327 A384328 A384329 * A384331 A384332 A384333

Keyword

nonn

Author

Darío Clavijo, May 26 2025

Extensions

More terms from Jinyuan Wang, May 26 2025

Status

approved