OFFSET
1,2
COMMENTS
Add 1 to each entry if you consider the empty set to be a semigroup as some people do. This was motivated by a question on the Mathfun Mailing List by Keith F. Lynch, asking for the number of subsemigroups of the multiplicative semigroup of Z/(n) that are groups.
LINKS
David W. Wilson, Table of n, a(n) for n = 1..119
David A. Corneth, PARI program
Edwin Hewitt and Herbert S. Zuckerman, The multiplicative semigroup of integers modulo m, Pacific J. Math., Vol. 10, 1960.
FORMULA
a(p) = 2*tau(p-1) + 1 for prime p. - Andrew Howroyd, Jun 28 2018
EXAMPLE
For n = 2 the 3 subsemigroups of Z/(2) under multiplication are {0},{1},{0,1}.
MAPLE
a:=proc(n)
local A, i, j, S, c, x;
A:=Matrix(n):
for i from 1 to n do
for j from 1 to n do
A[i, j]:=(i-1)*(j-1) mod n +1;
od:
od:
S:=combinat:-powerset(n):
c:=0;
for x in S do
if nops(x) = 0 then next; fi;
if Magma:-IsSubMagma(x, A) then c:=c+1; fi;
od;
return c;
end proc:
PROG
(PARI) \\ See PARI link. - David A. Corneth, Jun 26 2018
(Python)
from itertools import chain, combinations, combinations_with_replacement
for i in range(1, 100):
t = 0
for s in chain.from_iterable(combinations((list(range(0, i))), r) for r in range(1, i+1)):
c = 1
for k in combinations_with_replacement(s, 2):
if (k[0]*k[1])%i not in s:
c = 0
break
if c == 1:
t += 1
print(t, end=', ') # Gleb Ivanov, Oct 07 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
W. Edwin Clark, Apr 22 2016
EXTENSIONS
a(21)-a(39) from David A. Corneth, Jun 26 2018
a(40)-a(64) from Andrew Howroyd, Jun 28 2018
STATUS
approved