cp's OEIS Frontend

A374770 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.

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