A037144 Numbers with at most 3 prime factors (counted with multiplicity).

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 85, 86

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Complement of A033987: A001222(a(n))<=3; A117358(a(n))=1. - Reinhard Zumkeller, Mar 10 2006

Also numbers such that exist permutations of all proper divisors only with coprime adjacent elements: A178254(a(n))>0. - Reinhard Zumkeller, May 24 2010

Links

• Klaus Brockhaus, Table of n, a(n) for n = 1..10000

Crossrefs

A037143 is a subsequence.

Cf. A033987, A001222, A117358, A128644.

Programs

Magma

[ n: n in [1..86] | n eq 1 or &+[ t[2]: t in Factorization(n) ] le 3 ]; /* Klaus Brockhaus, Mar 20 2007 */

Mathematica

Select[Range[100],PrimeOmega[#]<4&] (* Harvey P. Dale, Oct 15 2015 *)

PARI

is(n)=bigomega(n)<4 \\ Charles R Greathouse IV, Sep 14 2015

Python

from math import prod, isqrt
from sympy import primerange, integer_nthroot, primepi
def A037144(n):
    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
    return kmax # Chai Wah Wu, Aug 23 2024

Formula

a(n) ~ 2n log n/(log log n)^2. - Charles R Greathouse IV, Sep 14 2015

Extensions

More terms from Reinhard Zumkeller, Mar 10 2006

More terms from Klaus Brockhaus, Mar 20 2007