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.

1, 3, 4, 11, 6, 24, 8, 59, 40, 68, 12, 284, 14, 192, 384, 795, 18, 1590, 20, 2876, 2552, 2192, 24, 17972, 3156, 8388, 20560, 35620, 30, 116474, 32, 144091, 178512, 131396, 94968, 1118426, 38, 524688, 1596560, 2569884, 42, 7280934, 44

Offset: 1

Author

Rémy Sigrist, Jul 19 2024

Keywords

• nonn
• more

Examples

			For n = 8: the principal subsets x (unique up to translation) alongside an appropriate subset y and the number of distinct translations are:
  x                  y                  #
  -----------------  -----------------  -
  {0}                {0,1,2,3,4,5,6,7}  8
  {0,1}              {0,2,4,6}          8
  {0,2}              {0,1,4,5}          8
  {0,3}              {0,2,4,6}          8
  {0,4}              {0,1,2,3}          4
  {0,1,2,3}          {0,4}              8
  {0,2,3,5}          {0,4}              8
  {0,1,4,5}          {0,2}              4
  {0,2,4,6}          {0,1}              2
  {0,1,2,3,4,5,6,7}  {0}                1
So a(8) = 8 + 8 + 8 + 8 + 4 + 8 + 8 + 4 + 2 + 1 = 59.
		

Links

• Rémy Sigrist, C++ program

Crossrefs

Cf. A045654, A056045, A374712.

Programs

Python

from itertools import combinations
from sympy import divisors, isprime
def A374770(n):
    if isprime(n): return n+1
    s = {}
    for d in divisors(n,generator=True):
        t = {}
        for a in combinations(range(n),d):
            for i in range(1,n):
                if (w:=tuple((i+b)%n for b in a)) in t:
                    t[w]+=1
                    break
            else:
                t[a] = 1
        s[d] = t
    c = 0
    for d in divisors(n,generator=True):
        for a in s[d]:
            for b in s[n//d]:
                if len({(x+y)%n for x in a for y in b})==n:
                    c += s[d][a]
                    break
    return c # Chai Wah Wu, Jul 22 2024

Formula

a(p) = p + 1 for any prime number p.

a(n) <= A056045(n).