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

Author

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

Keywords

• nonn

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

Crossrefs

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

Programs

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

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

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

Extensions

Formula and more terms from Vladeta Jovovic, Dec 03 2001

Offset corrected by Ray Chandler, May 30 2012