A123066 (Number of numbers <= n with an odd number of distinct prime factors) - (number of numbers <= n with an even number of distinct prime factors).

0, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 5, 4, 5, 6, 5, 6, 5, 4, 3, 4, 3, 4, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1, 2, 1, 2, 1, 0, -1, 0, -1, -2, -3, -4, -5, -4, -3, -2, -3, -4, -3, -4, -3, -2, -3, -4, -3, -2, -3, -2, -3, -4, -5, -6, -5, -4, -5, -4, -5, -4, -3, -4, -5, -6, -7, -6, -5, -6, -7, -8, -9, -10

Offset: 1

Author

Franklin T. Adams-Watters, Sep 26 2006

Keywords

• easy
• look
• sign

Comments

Analog of A072203 for number of distinct factors. Conjecture that sequence changes sign infinitely often, although the next sign change is probably large.

The signs first change at n = 52 and then change again at n = 7954. - Harvey P. Dale, Jul 04 2012

Links

• G. C. Greubel, Table of n, a(n) for n = 1..5000
• H. Helfgott and A. Ubis, Primos, paridad y análisis, arXiv:1812.08707 [math.NT], Dec. 2018.

Crossrefs

Cf. A030230, A030231.

Cf. A072203, A001221.

Cf. A346617.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 0, a(n-1)+
      `if`(nops(ifactors(n)[2])::odd, 1, -1))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Dec 21 2018

Mathematica

dpf[n_] := Module[{df = PrimeNu[n]}, If[OddQ[df], 1, -1]]; Join[{0}, Accumulate[ Array[dpf, 100, 2]]] (* Harvey P. Dale, Jul 04 2012 *)

Python

from sympy import primenu
def A123066(n): return 1+sum(1 if primenu(i)&1 else -1 for i in range(1,n+1)) # Chai Wah Wu, Dec 31 2022

Formula

a(n) = Sum_{k>=1} (-1)^(k-1) * A346617(n,k). - Alois P. Heinz, Aug 19 2021