cp's OEIS Frontend

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

%I A055037 #32 Aug 18 2025 05:50:20
%S A055037 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,
%T A055037 13,13,14,15,16,17,17,18,19,20,20,20,20,20,20,21,21,21,22,22,23,23,23,
%U A055037 24,25,26,27,28,28,29,29,30,30,31,32,32,32,32,33,33,33,33,33,34,34,34
%N A055037 Number of numbers <= n with an even number of prime factors (counted with multiplicity).
%C A055037 Partial sums of A065043.
%D A055037 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 92.
%H A055037 Vaclav Kotesovec, <a href="/A055037/b055037.txt">Table of n, a(n) for n = 1..10000</a>
%H A055037 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PolyaConjecture.html">Polya Conjecture</a>
%F A055037 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 A055037 Table[Length[Select[Range[n], EvenQ[PrimeOmega[#]] &]], {n, 75}] (* _Alonso del Arte_, May 28 2012 *)
%t A055037 Accumulate[Table[(LiouvilleLambda[n] + 1)/2, {n, 1, 100}]] (* _Vaclav Kotesovec_, Aug 18 2025 *)
%o A055037 (PARI) first(n)=my(s); vector(n,k,s+=1-bigomega(k)%2) \\ _Charles R Greathouse IV_, Sep 02 2015
%o A055037 (Python)
%o A055037 from functools import reduce
%o A055037 from operator import ixor
%o A055037 from sympy import factorint
%o A055037 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
%Y A055037 Cf. A001222, A002819, A008836, A055038, A065043.
%K A055037 nonn
%O A055037 1,4
%A A055037 Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), Jun 01 2000
%E A055037 Formula and more terms from _Vladeta Jovovic_, Dec 03 2001
%E A055037 Offset corrected by _Ray Chandler_, May 30 2012