cp's OEIS Frontend

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

%I A055038 #37 Jul 14 2025 06:09:49
%S A055038 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,
%T A055038 16,17,18,19,19,19,19,19,20,20,20,20,21,22,23,24,25,25,26,27,27,28,28,
%U A055038 29,30,30,30,30,30,30,31,31,32,32,33,33,33,34,35,36,36,37,38,39,40,40,41
%N A055038 Number of numbers <= n with an odd number of prime factors (counted with multiplicity).
%C A055038 Partial sums of A066829.
%D A055038 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 92.
%H A055038 Reinhard Zumkeller, <a href="/A055038/b055038.txt">Table of n, a(n) for n = 1..10000</a>
%H A055038 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PolyaConjecture.html">Polya Conjecture</a>
%F A055038 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).
%t A055038 Boole[OddQ[PrimeOmega[#]]]& /@ Range[100] // Accumulate (* _Jean-François Alcover_, Nov 21 2019 *)
%o A055038 (Haskell)
%o A055038 a055038 n = a055038_list !! (n-1)
%o A055038 a055038_list = scanl1 (+) a066829_list
%o A055038 -- _Reinhard Zumkeller_, Nov 19 2011
%o A055038 (PARI) first(n)=my(s); vector(n,k,s+=bigomega(k)%2) \\ _Charles R Greathouse IV_, Sep 02 2015
%o A055038 (Python)
%o A055038 from operator import ixor
%o A055038 from functools import reduce
%o A055038 from sympy import factorint
%o A055038 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
%Y A055038 Cf. A001222, A002819, A008836, A055037, A066829.
%K A055038 nonn
%O A055038 1,3
%A A055038 Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), Jun 01 2000
%E A055038 Formula and more terms from _Vladeta Jovovic_, Dec 03 2001
%E A055038 Offset corrected by _Reinhard Zumkeller_, Nov 19 2011