To extend A018216 Maximal number of subgroups in a group with n elements

[Max Alekseyev]

Maximilian,

Thanks for the reference!
I've implemented the formula from that paper in PARI/GP. My
implementation is attached (nsg.gp). With it we can easily get yet
another way to compute A006116:

{ A006116(n) = numsubgrp(2,vector(n,i,1)) }

and A061034 (see below). Thousands of terms of A061034 can be obtained
in a matter of seconds now. Here is the first hundred:

1, 2, 2, 5, 2, 4, 2, 16, 6, 4, 2, 10, 2, 4, 4, 67, 2, 12, 2, 10, 4, 4,
2, 32, 8, 4, 28, 10, 2, 8, 2, 374, 4, 4, 4, 30, 2, 4, 4, 32, 2, 8, 2,
10, 12, 4, 2, 134, 10, 16, 4, 10, 2, 56, 4, 32, 4, 4, 2, 20, 2, 4, 12,
2825, 4, 8, 2, 10, 4, 8, 2, 96, 2, 4, 16, 10, 4, 8, 2, 134, 212, 4, 2,
20, 4, 4, 4, 32, 2, 24, 4, 10, 4, 4, 4, 748, 2, 20, 12, 40

Neil, please fill up A061034 with the terms.

Regards,
Max

P.S. This is implementation of A061034:

{ A061034(n) = local(f=factorint(n)); prod(i=1,matsize(f)[1],
A061034pp(f[i,1],f[i,2]) ) }

\\ for prime power p^k
{ A061034pp(p,k) = res=0; for(i=1, k, aux_part(p, k-i, i, [])); res }

\\ iterate over all partitions
{ aux_part(p, n, m, v) =
  v = concat(v,m);
  if(n,
    for(i=1, min(m,n), aux_part(p, n-i, i, v))
    ,
    res=max(res,numsubgrp(p,v));
  );
}


On Dec 3, 2007 5:55 AM, Maximilian Hasler <maximilian.hasler at gmail.com> wrote:
> You could add the reference:
>
>     On the Subgroups of an Abelian Group
>         G. A. Miller
>         The Annals of Mathematics, 2nd Ser., Vol. 6, No. 1. (Oct.,
> 1904), pp. 1-6.
>
>         Stable URL:
> http://links.jstor.org/sici?sici=0003-486X%28190410%292%3A6%3A1%3C1%3AOTSOAA%3E2.0.CO%3B2-P
>
> Paragraph 4 is entitled "total number of subgroups in a group of order p^m"
>
> Maximilian
>
>
>
> On Dec 1, 2007 9:27 PM, Max Alekseyev <maxale at gmail.com> wrote:
> > On Nov 30, 2007 4:41 PM, Christian G. Bower <bowerc at usa.net> wrote:
> > > I think C2^4 has 67 subgroups (1 trivial, 15 C2, 35 C2^2, 15 C2^3, 1 itself).
> > > I would suspect that's the largest case, but I'm not in the mood to check all
> > > 14 groups of order 16 (and to dig up a description of the more obsure ones.)
> >
> > I've checked all abelian groups of order 16 and A006116(4)=67 is
> > indeed the largest case:
> >
> > C16 has 5 subgroups
> > C2 x C8 has 11 subgroups
> > (C2)^2 x C4 has 27 subgroups
> > (C2)^4 has 67 subgroups
> > (C4)^2 has 15 subgroups
> >
> > This gives boost to A061034:
> >
> > %S A061034 1,2,2,5,2,  4,2,16,6,4,  2,10,2,4,4, 67,2,12,2,10, 4,4,2,32,8, 4,28,10,2,8,  2
> >
> > Neil, please update A061034 accordingly.
> >
> > Regards,
> > Max
> >
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: nsg.gp
Type: application/octet-stream
Size: 1154 bytes
Desc: not available
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20071203/7915ec94/attachment-0001.obj>