login
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.
1

%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