%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