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.

Links

Table of n, a(n) for n=1..76.

Eric Weisstein's World of Mathematics, Polya Conjecture

Formula

(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 *)

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

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