|
|
A196021
|
|
Number of subsets T of S={0,1,2,...,n-1} such that the closure of T under addition modulo n is S.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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.
|
|
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, {}):
|
|
PROG
|
(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, [])
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|