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

Offset: 1

Author

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

Keywords

• nonn

Comments

Partial sums of A066829.

References

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Polya Conjecture

Crossrefs

Cf. A001222, A002819, A008836, A055037, A066829.

Programs

Haskell

a055038 n = a055038_list !! (n-1)
a055038_list = scanl1 (+) a066829_list
-- Reinhard Zumkeller, Nov 19 2011

Mathematica

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

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

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