A087671 Number of subsets S of {0,1,2,...,n-1} which are idempotent under squaring modulo n, where S*S mod n = {x*y mod n|x,y in S}.

2, 4, 6, 8, 8, 27, 10, 26, 18, 43, 10, 146, 14, 59, 107, 114, 12, 184, 14, 406, 142, 59, 10, 1618, 52, 100, 200, 1046, 14, 2765, 18

Offset

1,1

Links

Table of n, a(n) for n=1..31.

Example

{4} is one of the a(6) = 27 idempotent (mod 6) subsets of {0,1,2,3,4,5}, since {4}*{4} = {16 mod 6} = {4}.

Prog

(Python)
from itertools import chain, combinations
def powerset(s):
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def cond(s, n):
    return set(s)==set((si*sj)%n for i, si in enumerate(s) for sj in s[i:])
def a(n):
    return sum(1 for s in powerset(range(n)) if cond(s, n))
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Feb 01 2022
(PARI) idemp(s, n) = {my(ss = setbinop((x, y)->x*y % n, s), j); if ((j=setsearch(ss, 0)), ss[j] = n; ss = Set(ss)); s == ss; }
a(n) = {my(nb=0); forsubset(n, s, if (idemp(Vec(s), n), nb++); ); nb; } \\ Michel Marcus, Feb 01 2022

Crossrefs

Sequence in context: A333557 A062355 A366602 * A088308 A167832 A134488

Adjacent sequences: A087668 A087669 A087670 * A087672 A087673 A087674

Keyword

nonn,more

Author

John W. Layman, Sep 26 2003

Extensions

a(26)-a(31) from Michael S. Branicky, Feb 01 2022

Status

approved