A066829 Parity of Omega(n): a(n) = 1 if n is the product of an odd number of primes; 0 if product of even number of primes.

0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0

Offset

1,1

Comments

a(A026424(n)) = 1; a(A028260(n)) = 0.

From Reinhard Zumkeller, Jul 01 2009: (Start)

The first N Terms are constructed by the following sieving process:

for j:=1 until N do a(j):=0,

for i:=1 until N/2 do

for j:=2*i step i until N do a(j):=1-a(i). (End)

Omega is also written in the OEIS as bigomega. See also comments, references and formulas in A008836 (Liouville's lambda), A007421 and A065043, that all contain the same information as this sequence. - Antti Karttunen, Apr 30 2022

Links

Antti Karttunen, Table of n, a(n) for n = 1..100000 (first 10000 terms from Reinhard Zumkeller)

S. Ramanujan, Irregular numbers, J. Indian Math. Soc., 5 (1913), 105-106; Coll. Papers 20-21 (provides Dirichlet g.f.)

Index entries for characteristic functions

Index entries for sequences computed from exponents in factorization of n

Index entries for sequences generated by sieves

Formula

Dirichlet g.f.: (zeta(s)^2 - zeta(2*s)) / (2*zeta(s)). [Typo corrected by Vaclav Kotesovec, Jan 30 2024]

a(n) = (1-A008836(n)) / 2. - Corrected by Antti Karttunen, Apr 30 2022

a(m*n) = a(m) XOR a(n). - Reinhard Zumkeller, Aug 28 2008

a(n) = A001222(n) mod 2. - Reinhard Zumkeller, Nov 19 2011

From Antti Karttunen, May 01 & Nov 30 2022: (Start)

a(n) = 1 - A065043(n) = A349905(n) mod 2.

a(n) = A353556(n) + A353558(n).

a(n) = A358751(n) + A358753(n).

(End)

Example

From Reinhard Zumkeller, Jul 01 2009: (Start)
Sieve for N = 30, also demonstrating the affinity to the Sieve of Eratosthenes:
[initial] a(j):=0, 1<=j<=30:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
[i=1] a(1)=0 --> a(j):=1, 2<=j<=30:
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[i=2] a(2)=1 --> a(2*j):=0, 2<=j<=[30/2]:
0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
[i=3] a(3)=1 --> a(3*j):=0, 2<=j<=[30/3]:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
[i=4] a(4)=0 --> a(4*j):=1, 2<=j<=[30/4]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0
[i=5] a(5)=1 --> a(5*j):=0, 2<=j<=[30/5]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0
[i=6] a(6)=0 --> a(6*j):=1, 2<=j<=[30/6]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1
[i=7] a(7)=1 --> a(7*j):=0, 2<=j<=[30/7]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 1 1
[i=8] a(8)=1 --> a(8*j):=0, 2<=j<=[30/8]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1
[i=9] a(9)=0 --> a(9*j):=1, 2<=j<=[30/9]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1
[i=10] a(10)=0 --> a(10*j):=1, 2<=j<=[30/10]:
0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 1
and so on: a(22):=0 in [i=11], a(24):=0 in [i=12], a(26):=0 in [i=13], a(28):=1 in [i=14], and a(30):=1 in [i=15]. (End)

Maple

A066829 := proc(n)
    modp(numtheory[bigomega](n) , 2) ;
end proc:
seq(A066829(n), n=1..80) ; # R. J. Mathar, Jul 15 2017

Mathematica

Table[(1-LiouvilleLambda[n])/2, {n, 1, 20}] (* Enrique Pérez Herrero, Jul 07 2012 *)
Table[If[OddQ[PrimeOmega[n]], 1, 0], {n, 120}] (* Harvey P. Dale, Mar 12 2016 *)

Prog

(PARI) A066829(n) = (bigomega(n)%2); \\ Simplified by Antti Karttunen, Apr 30 2022
(Haskell)
a066829 = (`mod` 2) . a001222 -- Reinhard Zumkeller, Nov 19 2011
(Python)
from sympy import primeomega as Omega
def a(n): return Omega(n)%2
print([a(n) for n in range(1, 105)]) # Michael S. Branicky, Apr 30 2022
(Python)
from operator import ixor
from functools import reduce
from sympy import factorint
def A066829(n): return reduce(ixor, factorint(n).values(), 0)&1 # Chai Wah Wu, Jan 01 2023

Crossrefs

Characteristic function of A026424 (positions of 1's). Cf. also A028260 (its complement, positions of 0's).

Cf. A001222 (bigomega), A007421, A008836, A055038 (partial sums), A065043, A069545 (run lengths), A072203, A349905, A353556, A353558, A358751, A358753.

Sequence in context: A359158 A099104 A358769 * A194664 A285975 A213729

Adjacent sequences: A066826 A066827 A066828 * A066830 A066831 A066832

Keyword

nonn,easy

Author

G. L. Honaker, Jr., Jan 17 2002

Extensions

Corrected and comment added by Reinhard Zumkeller, Jun 26 2009

Status

approved