A055037 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

(list; graph; refs; listen; history; text; internal format)

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