login
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.
1

%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