%I #14 Jul 22 2024 15:20:31
%S 1,3,4,11,6,24,8,59,40,68,12,284,14,192,384,795,18,1590,20,2876,2552,
%T 2192,24,17972,3156,8388,20560,35620,30,116474,32,144091,178512,
%U 131396,94968,1118426,38,524688,1596560,2569884,42,7280934,44
%N a(n) is the number of subsets x of Z_n such that #x * #y = n and x + y = Z_n for some subset y of Z_n.
%H Rémy Sigrist, <a href="/A374770/a374770.txt">C++ program</a>
%F a(p) = p + 1 for any prime number p.
%F a(n) <= A056045(n).
%e For n = 8: the principal subsets x (unique up to translation) alongside an appropriate subset y and the number of distinct translations are:
%e x y #
%e ----------------- ----------------- -
%e {0} {0,1,2,3,4,5,6,7} 8
%e {0,1} {0,2,4,6} 8
%e {0,2} {0,1,4,5} 8
%e {0,3} {0,2,4,6} 8
%e {0,4} {0,1,2,3} 4
%e {0,1,2,3} {0,4} 8
%e {0,2,3,5} {0,4} 8
%e {0,1,4,5} {0,2} 4
%e {0,2,4,6} {0,1} 2
%e {0,1,2,3,4,5,6,7} {0} 1
%e So a(8) = 8 + 8 + 8 + 8 + 4 + 8 + 8 + 4 + 2 + 1 = 59.
%o (C++) // See Links section.
%o (Python)
%o from itertools import combinations
%o from sympy import divisors, isprime
%o def A374770(n):
%o if isprime(n): return n+1
%o s = {}
%o for d in divisors(n,generator=True):
%o t = {}
%o for a in combinations(range(n),d):
%o for i in range(1,n):
%o if (w:=tuple((i+b)%n for b in a)) in t:
%o t[w]+=1
%o break
%o else:
%o t[a] = 1
%o s[d] = t
%o c = 0
%o for d in divisors(n,generator=True):
%o for a in s[d]:
%o for b in s[n//d]:
%o if len({(x+y)%n for x in a for y in b})==n:
%o c += s[d][a]
%o break
%o return c # _Chai Wah Wu_, Jul 22 2024
%Y Cf. A045654, A056045, A374712.
%K nonn,more
%O 1,2
%A _Rémy Sigrist_, Jul 19 2024