login
Number of groups of order A037144(n).
6

%I #15 Aug 24 2024 05:56:50

%S 1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,1,5,1,5,2,2,1,2,2,5,4,1,4,1,1,2,1,1,2,

%T 2,1,6,1,4,2,2,1,2,5,1,5,1,2,2,2,1,1,2,4,1,4,1,5,1,4,1,1,2,3,4,1,6,1,

%U 2,1,1,2,1,1,1,4,2,2,1,1,5,2,1,4,1,2,2,1,1,6,2,1,6,1,5,4,2,1,2,2,1,4,5,1,2

%N Number of groups of order A037144(n).

%C Number of groups whose order has at most 3 prime factors.

%C The groups of these orders (up to A037144(473273456) = 1073741821 in version V2.13-4) form a class contained in the Small Groups Library of MAGMA.

%H Klaus Brockhaus, <a href="/A128644/b128644.txt">Table of n, a(n) for n=1..10000</a>

%H MAGMA Documentation, <a href="http://magma.maths.usyd.edu.au/magma/htmlhelp/text404.htm">Database of Small Groups</a>

%F a(n) = A000001(A037144(n)).

%e A037144(17) = 18 and there are 5 groups of order 18 (A000001(18) = 5), hence a(17) = 5.

%o (Magma) D:=SmallGroupDatabase(); [ NumberOfSmallGroups(D, n) : n in [ h: h in [1..130] | h eq 1 or &+[ t[2]: t in Factorization(h) ] le 3 ] ];

%o (PARI) /* based on the formulas from Mitch Harris in A000001 */ {ngoam3pf(n) = local(f, g, nf, ng, p, q, r, qmp, rmp, rmq); f=factor(n); nf=matsize(f)[1]; g=sum(i=1, nf, f[i, 2]); if(g<1, ng=1, if(g>3, ng=-1, if(nf==1, if(f[1, 2]==1, ng=1, if(f[1, 2]==2, ng=2, if(f[1, 2]==3, ng=5, ng=-1))), if(nf==2, if(f[1, 2]*f[2, 2]==1, if(gcd(f[1, 1], f[2, 1]-1)==1, ng=1, ng=2), if(f[1, 2]==1, p=f[1, 1]; q=f[2, 1], q=f[1, 1]; p=f[2, 1]); if(p==2&&q%2>0, ng=5, if(q%p==1&&p%2>0, ng=(p+9)/2, if(p==3&&q==2, ng=5, if(p%2>0&&q%2>0&&q%p==p-1, ng=3, if(p>3&&p%q==1&&p%q^2!=1, ng=4, if(p%q^2==1, ng=5, if(q%p!=1&&q%p!=(p-1)&&p%q!=1, ng=2)))))))), p=f[1, 1]; q=f[2, 1]; r=f[3, 1]; qmp=q%p==1; rmp=r%p==1; rmq=r%q==1; if(qmp, if(rmp, if(rmq, ng=p+4, ng=p+2), if(rmq, ng=3, ng=2)), if(rmp, if(rmq, ng=4, ng=2), if(rmq, ng=2, ng=1))))))); return(ng)}

%o for(n=1, 100, k=ngoam3pf(n); if(k>=0, print1(k, ",")))

%o (Python)

%o from itertools import combinations

%o from math import prod, isqrt

%o from sympy import primerange, integer_nthroot, primepi, factorint

%o def A128644(n):

%o if n == 1: return 1

%o def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b,isqrt(x//c)+1),a)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b,integer_nthroot(x//c,m)[0]+1),a) for d in g(x,a2,b2,c*b2,m-1)))

%o def f(x): return int(n+x-2-primepi(x)-sum(sum(primepi(x//prod(c[1] for c in a))-a[-1][0] for a in g(x,0,1,1,i)) for i in range(2,4)))

%o kmin, kmax = 1,2

%o while f(kmax) >= kmax:

%o kmax <<= 1

%o while True:

%o kmid = kmax+kmin>>1

%o if f(kmid) < kmid:

%o kmax = kmid

%o else:

%o kmin = kmid

%o if kmax-kmin <= 1:

%o break

%o fs = factorint(kmax)

%o if max(fs.values()) == 1:

%o a = set(fs.keys())

%o return sum(prod((p**sum(1 for q in b if q%p==1)-1)//(p-1) for p in a-set(b)) for l in range(0, len(a)+1) for b in combinations(a, l))

%o if len(fs)==1: return 3*list(fs.values())[0]-4

%o p, q = list(fs.keys())

%o if fs[p] > 1: p, q = q, p

%o if q%p==1 and p&1: return p+9>>1

%o r = (p-1)%(q**2)

%o if (p==3 and q==2) or (p==2 and q&1) or not r: return 5

%o if not (p-1)%q and p>3 and r: return 4

%o if not (q+1)%p and p&1 and q&1: return 3

%o if (q+1)%p and (q-1)%p and (p-1)%q: return 2 # _Chai Wah Wu_, Aug 23 2024

%Y Cf. A000001 (number of groups of order n), A037144 (numbers with at most 3 prime factors), A128604 (number of groups whose order divides p^6 for p a prime).

%K nonn

%O 1,4

%A _Klaus Brockhaus_, Mar 20 2007