A128644 Number of groups of order A037144(n).

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, 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, 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

Offset: 1

Author

Klaus Brockhaus, Mar 20 2007

Keywords

• nonn

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.

Examples

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

Links

• Klaus Brockhaus, Table of n, a(n) for n=1..10000
• Magma Computational Algebra System, Documentation, see Database of Small Groups.

Crossrefs

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).

Programs

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

Formula

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