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

%I #28 Nov 22 2023 22:14:25

%S 1,1,4,5,16,22,64,109,283,486,1189,2174,5097,9528,21904,41549,92022,

%T 177043,387715,754910,1624543,3174095,6751375,13296454,27962241,

%U 55173405,115220461,228121892,472419049,937688232,1930884229,3840200525,7867929073,15660179800

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

%F a(n) >= A058622(n). - _Michael Chu_, Oct 27 2023

%e 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.

%p sums:= (s, n)-> {seq(seq(irem(i+j, n), j=s), i=s)}:

%p b:= (i, n, s)-> `if`(sums(s, n) = {$0..(n-1)}, 2^(n-i),

%p `if`(i=n, 0, b(i+1, n, s) +b(i+1, n, {s[], i}))):

%p a:= n-> b(0, n, {}):

%p seq(a(n), n=1..15); # _Alois P. Heinz_, Oct 21 2011

%o (Python)

%o def sums(s, n):

%o return sorted(set((si+sj)%n for i, si in enumerate(s) for sj in s[i:]))

%o def b(i, n, s):

%o if sums(s, n) == list(range(n)): return 2**(n-i)

%o if i == n: return 0

%o return b(i+1, n, s) + b(i+1, n, sorted(set(s+[i])))

%o def a(n): return b(0, n, [])

%o print([a(n) for n in range(1, 19)]) # _Michael S. Branicky_, Jan 09 2022 after _Alois P. Heinz_

%K nonn

%O 1,3

%A _John W. Layman_, Sep 26 2011

%E a(21)-a(28) from _Alois P. Heinz_, Oct 21 2011

%E a(29)-a(34) from _Michael S. Branicky_, Jan 09 2022