login
A272213
Number of distinct subsemigroups of the multiplicative semigroup of integers modulo n.
2
1, 3, 5, 8, 7, 26, 9, 29, 20, 42, 9, 168, 13, 58, 106, 141, 11, 220, 13, 504, 141, 58, 9, 1997, 66, 99, 279, 1420, 13, 2764, 17, 2171, 141, 83, 248, 12412, 19, 99, 258, 19549, 17, 4135, 17, 15508, 8310, 58, 9, 91508, 228, 1758, 226, 60303, 13, 26691, 248, 228792, 245, 99, 9, 890397, 25, 140, 109296, 389930
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 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
Sequence in context: A120098 A081859 A046086 * A225454 A131977 A139125
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