A055038 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

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

Sequence in context: A355538 A238884 A066683 * A373114 A276796 A309093

Adjacent sequences: A055035 A055036 A055037 * A055039 A055040 A055041

KEYWORD

nonn,changed

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