login
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
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,2
FORMULA
a(p) = p + 1 for any prime number p.
a(n) <= A056045(n).
EXAMPLE
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.
PROG
(C++) // See Links section.
(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
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Rémy Sigrist, Jul 19 2024
STATUS
approved