A055037 Number of numbers <= n with an even number of prime factors (counted with multiplicity).

1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 13, 13, 13, 13, 13, 13, 13, 14, 15, 16, 17, 17, 18, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 22, 22, 23, 23, 23, 24, 25, 26, 27, 28, 28, 29, 29, 30, 30, 31, 32, 32, 32, 32, 33, 33, 33, 33, 33, 34, 34, 34

Offset

1,4

Comments

Partial sums of A065043.

References

James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 92.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Polya Conjecture

Formula

a(n) = (1/2)*Sum_{k=1..n} (1+lambda(k)) = (1/2)*(n+L(n)), where lambda(n)=A008836(n) and L(n)=A002819(n).

Mathematica

Table[Length[Select[Range[n], EvenQ[PrimeOmega[#]] &]], {n, 75}] (* Alonso del Arte, May 28 2012 *)
Accumulate[Table[(LiouvilleLambda[n] + 1)/2, {n, 1, 100}]] (* Vaclav Kotesovec, Aug 18 2025 *)

Prog

(PARI) first(n)=my(s); vector(n, k, s+=1-bigomega(k)%2) \\ Charles R Greathouse IV, Sep 02 2015
(Python)
from functools import reduce
from operator import ixor
from sympy import factorint
def A055037(n): return sum(1 for i in range(1, n+1) if not (reduce(ixor, factorint(i).values(), 0)&1)) # Chai Wah Wu, Jan 01 2023
(Python)
from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A055037(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)))
    return int(1+sum(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n, 0, 1, 1, m)) for m in range(2, n.bit_length()+1, 2))) # Chai Wah Wu, Dec 19 2025

Crossrefs

Cf. A001222, A002819, A008836, A055038, A065043.

Sequence in context: A316628 A153112 A005350 * A227386 A351833 A354967

Adjacent sequences: A055034 A055035 A055036 * A055038 A055039 A055040

Keyword

nonn

Author

Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), Jun 01 2000

Extensions

Formula and more terms from Vladeta Jovovic, Dec 03 2001

Offset corrected by Ray Chandler, May 30 2012

Status

approved