A196021 Number of subsets T of S={0,1,2,...,n-1} such that the closure of T under addition modulo n is S.

1, 1, 4, 5, 16, 22, 64, 109, 283, 486, 1189, 2174, 5097, 9528, 21904, 41549, 92022, 177043, 387715, 754910, 1624543, 3174095, 6751375, 13296454, 27962241, 55173405, 115220461, 228121892, 472419049, 937688232, 1930884229, 3840200525, 7867929073, 15660179800

Offset: 1

Author

John W. Layman, Sep 26 2011

Keywords

• nonn

Examples

			For n = 3, each of the four subsets {0,1}, {0,2}, {1,2}, and {0,1,2} has closure {0,1,2} under addition modulo 3 (for example, {0,2} + {0,2} = {0,2,4} = {0,1,2} modulo 3).  Thus a(3) = 4.
		

Programs

Maple

sums:= (s, n)-> {seq(seq(irem(i+j, n), j=s), i=s)}:
b:= (i, n, s)-> `if`(sums(s, n) = {$0..(n-1)}, 2^(n-i),
                `if`(i=n, 0, b(i+1, n, s) +b(i+1, n, {s[], i}))):
a:= n-> b(0, n, {}):
seq(a(n), n=1..15);  # Alois P. Heinz, Oct 21 2011

Python

def sums(s, n):
    return sorted(set((si+sj)%n for i, si in enumerate(s) for sj in s[i:]))
def b(i, n, s):
    if sums(s, n) == list(range(n)): return 2**(n-i)
    if i == n: return 0
    return b(i+1, n, s) + b(i+1, n, sorted(set(s+[i])))
def a(n): return b(0, n, [])
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Jan 09 2022 after Alois P. Heinz

Formula

a(n) >= A058622(n). - Michael Chu, Oct 27 2023

Extensions

a(21)-a(28) from Alois P. Heinz, Oct 21 2011

a(29)-a(34) from Michael S. Branicky, Jan 09 2022