%I #17 Nov 28 2014 12:07:35
%S 0,1,1,3,0,4,3,3,1,7,2,7,1,3,4,8,1,11,2,3,2,9,2,7,1,9,2,15,0,13,7,3,1,
%T 7,2,11,3,3,2,19,1,15,2,5,2,11,2,13,1,3,3,15,2,7,4,5,2,15,1,15,1,6,8,
%U 7,1,15,5,3,1,29,3,14,2,5,4,9,2,23,3,13,1,15
%N Let D = {d(n,i)}, i = 1..q, denote the set of divisors of n; then a(n) = number of multiplicative groups G(n,p) = D/kZ, 1 < k < n.
%C We introduce the structure of a finite group in order to study the divisors of each integer.
%C We see that the study of the classification of the divisors is dependent on the values k. The trivial group {1} is counted.
%C The principle of the algorithm is to compute all the products d(n,i)/kZ * d(n,j)/kZ and also the inverse of each element such that if x is in the group, then there exists x’ in the group with x*x’ = 1.
%C An interesting property: a(n)= 0 for n = 2, 6, 30, 186, 366, 426, 606, 786, 1266, 1446, 1626, 1686, ... where n>30 is of the form n = 6*q with q prime of the form (10*k + 1) => q = 31, 61, 71, 101, 131, 211, 241, 271, 281, 311, 421, 491, ...
%C a(n) = 1 for n = 3, 4, 10, 14, 18, 26, 34, 42, 50, 60, 62, 66, ...
%H Michel Lagneau, <a href="/A245907/b245907.txt">Table of n, a(n) for n = 2..2000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FiniteGroup.html">Finite Group</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Finite_group">Finite group</a>
%e a(133) = 11 because there exist eleven finite groups formed from the four divisors {1,7,19,133} of 133. The eleven finite groups G(133,p) are:
%e G(133,2) = {1}
%e G(133,3} = {1}
%e G(133,4} = {1,3}
%e G(133,5} = {1,2,3,4}
%e G(133,6} = {1}
%e G(133,8} = {1,3,5,7}
%e G(133,10} = {1,3,7,9}
%e G(133,12} = {1,7}
%e G(133,15} = {1,4,7,13}
%e G(133,24} = {1,7,13,19}
%e G(133,30} = {1,7,13,19}
%p with(numtheory):
%p for n from 2 to 100 do:
%p x:=divisors(n):n1:=nops(x):ind:=0:
%p for p from 2 to n-1 do:
%p lst:={}:
%p for i from 1 to n1 do:
%p lst:=lst union {irem(x[i],p)}:
%p od:
%p n2:=nops(lst):lst1:={}:
%p for a from 1 to n2 do:
%p for b from 1 to n2 do:
%p lst1:=lst1 union {irem(lst[a]*lst[b],p)}:
%p od:
%p od:
%p if lst1=lst
%p then
%p n3:=nops(lst1):lst2:={}:
%p for c from 1 to n3 do:
%p for d from 1 to n3 do:
%p if irem(lst1[c]*lst1[d],p)=1
%p then lst2:=lst2 union {lst1[c]}:
%p else
%p fi:
%p od:
%p od:
%p if lst2=lst
%p then
%p ind:=ind+1:
%p else
%p fi:
%p fi:
%p od:
%p printf(`%d, `,ind):
%p od:
%K nonn
%O 2,4
%A _Michel Lagneau_, Nov 13 2014