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

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

Formula

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

Mathematica

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

Prog

(Magma) [ n: n in [1..86] | n eq 1 or &+[ t[2]: t in Factorization(n) ] le 3 ]; /* Klaus Brockhaus, Mar 20 2007 */
(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

Crossrefs

A037143 is a subsequence.

Cf. A033987, A001222, A117358, A128644.

Sequence in context: A028261 A119675 A253781 * A337379 A121684 A191853

Adjacent sequences: A037141 A037142 A037143 * A037145 A037146 A037147

Keyword

nonn

Author

N. J. A. Sloane.

Extensions

More terms from Reinhard Zumkeller, Mar 10 2006

More terms from Klaus Brockhaus, Mar 20 2007

Status

approved