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

1, 1, 2, 3, 5, 9, 17, 30, 58, 107, 205, 392, 768, 1466, 2883, 5597, 11038, 21572, 42675, 83711, 166371, 327893, 651199, 1288480, 2564032, 5082878, 10127472, 20115845, 40104636, 79781149, 159174500, 316962113, 632716744, 1261189166, 2518287361, 5023170116, 10034132101, 20025033970

Offset: 1

Author

SiYang Hu, May 16 2025

Keywords

• nonn

Comments

Every subset S of [1..n] must have 1 and n to get 2 and 2*n. For odd n we therefore have 1+n which we need as well. If S is no such subset then no subset S' of S must be tested. - David A. Corneth, May 22 2025

Examples

			For n = 5, there are 5 sets S that satisfy the said conditions: {1, 2, 3, 4, 5}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5} and {1, 3, 5}.
		

Links

• David A. Corneth, PARI program
• Sean A. Irvine, Java program (github)

Programs

Python

def a(n):
    if n == 1: return 1
    c,t = 0, set(k << 1 for k in range(1, n+1))
    for i in range(1 << (n-2), 1 << n):
        s = [j+1 for j in range(n) if (i >> j) & 1]
        if s[0] == 1 and s[-1] == n:
            ss = set(x + y for x in s for y in s if x & 1 == y & 1)
            if t.issubset(ss): c += 1
    return c # Darío Clavijo, May 23 2025

Extensions

a(23)-a(38) from Sean A. Irvine, May 21 2025