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,3

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

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).

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
(Python)
from math import isqrt, prod
from sympy import primerange, integer_nthroot, primepi
def A055038(n):
    def g(x, a, b, c, m): yield from (((d, ) for d in enumerate(primerange(b, isqrt(x//c)+1), a)) if m==2 else (((a2, b2), )+d for a2, b2 in enumerate(primerange(b, integer_nthroot(x//c, m)[0]+1), a) for d in g(x, a2, b2, c*b2, m-1)))
    return n-1-sum(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n, 0, 1, 1, m)) for m in range(2, n.bit_length()+1, 2)) # Chai Wah Wu, Dec 19 2025

Crossrefs

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

Sequence in context: A238884 A066683 A384210 * 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