OFFSET
1,4
COMMENTS
Number of groups whose order has at most 3 prime factors.
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.
LINKS
Klaus Brockhaus, Table of n, a(n) for n=1..10000
MAGMA Documentation, Database of Small Groups
PROG
(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 ] ];
(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)}
for(n=1, 100, k=ngoam3pf(n); if(k>=0, print1(k, ", ")))
(Python)
from itertools import combinations
from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi, factorint
def A128644(n):
if n == 1: return 1
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)))
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)))
kmin, kmax = 1, 2
while f(kmax) >= kmax:
kmax <<= 1
while True:
kmid = kmax+kmin>>1
if f(kmid) < kmid:
kmax = kmid
else:
kmin = kmid
if kmax-kmin <= 1:
break
fs = factorint(kmax)
if max(fs.values()) == 1:
a = set(fs.keys())
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))
if len(fs)==1: return 3*list(fs.values())[0]-4
p, q = list(fs.keys())
if fs[p] > 1: p, q = q, p
if q%p==1 and p&1: return p+9>>1
r = (p-1)%(q**2)
if (p==3 and q==2) or (p==2 and q&1) or not r: return 5
if not (p-1)%q and p>3 and r: return 4
if not (q+1)%p and p&1 and q&1: return 3
if (q+1)%p and (q-1)%p and (p-1)%q: return 2 # Chai Wah Wu, Aug 23 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Klaus Brockhaus, Mar 20 2007
STATUS
approved