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

Author

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

Keywords

• nonn
• easy

Comments

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

Examples

			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)
		

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

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.

Cf. A000035.

Programs

Haskell

a066829 = (`mod` 2) . a001222 -- Reinhard Zumkeller, Nov 19 2011

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

PARI

A066829(n) = (bigomega(n)%2); \\ Simplified by Antti Karttunen, Apr 30 2022

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

Formula

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

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)

a(n) = A000035(A001222(n)). - Omar E. Pol, Apr 09 2025

Extensions

Corrected and comment added by Reinhard Zumkeller, Jun 26 2009