A055038 - OEIS

A055038

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

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

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

OFFSET

1,3

COMMENTS

Partial sums of A066829.

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

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

Boole[OddQ[PrimeOmega[#]]]& /@ Range[100] // Accumulate (* Jean-François Alcover, Nov 21 2019 *)

PROG

(Haskell)

a055038 n = a055038_list !! (n-1)

a055038_list = scanl1 (+) a066829_list

-- Reinhard Zumkeller, Nov 19 2011

(PARI) first(n)=my(s); vector(n, k, s+=bigomega(k)%2) \\ Charles R Greathouse IV, Sep 02 2015

(Python)

from operator import ixor

from functools import reduce

from sympy import factorint

def A055038(n): return sum(1 for i in range(1, n+1) if reduce(ixor, factorint(i).values(), 0)&1) # Chai Wah Wu, Jan 01 2023

CROSSREFS

Sequence in context: A355538 A238884 A066683 * A373114 A276796 A309093

Adjacent sequences: A055035 A055036 A055037 * A055039 A055040 A055041

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 Reinhard Zumkeller, Nov 19 2011

STATUS

approved