A087671 - OEIS

%I #11 Feb 01 2022 08:07:31

%S 2,4,6,8,8,27,10,26,18,43,10,146,14,59,107,114,12,184,14,406,142,59,

%T 10,1618,52,100,200,1046,14,2765,18

%N 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}.

%e {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}.

%o (Python)

%o from itertools import chain, combinations

%o def powerset(s):

%o     return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

%o def cond(s, n):

%o     return set(s)==set((si*sj)%n for i, si in enumerate(s) for sj in s[i:])

%o def a(n):

%o     return sum(1 for s in powerset(range(n)) if cond(s, n))

%o print([a(n) for n in range(1, 21)]) # _Michael S. Branicky_, Feb 01 2022

%o (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;}

%o a(n) = {my(nb=0); forsubset(n, s, if (idemp(Vec(s), n), nb++);); nb;} \\ _Michel Marcus_, Feb 01 2022

%K nonn,more

%O 1,1

%A _John W. Layman_, Sep 26 2003

%E a(26)-a(31) from _Michael S. Branicky_, Feb 01 2022