OFFSET
0
LINKS
Antti Karttunen, Table of n, a(n) for n = 0..8192
FORMULA
a(0)=1, a(1)=1, a(p)=A091225(p) for primes, and for composite n, a(n) = A091225(n) bitor (BITOR_{1<d<n,d|n} a(d)*a(n/d). [Here bitor stands for a dyadic bitwise-or function (A003986), and BITOR_{1<d<n,d|n} a cumulative version of the same, where d ranges over all proper factors of n. A091225 is a characteristic function for (binary codes of) irreducible polynomials in ring GF(2)[X], A014580.]
The same formula can be converted to a more standard notation with the help of De Morgan's laws:
a(0)=1, a(1)=1, a(p)=A091225(p) for primes, and for composite n, a(n) = 1 - ((1-A091225(n)) * (Product_{1<d<n,d|n} (1-(a(d)*a(n/d))))).
a(n) = 1 iff A236853(n) > 0. [The latter sequence should also have a similar formula like above ones, only more complex.]
EXAMPLE
a(5)=0 because the binary representation of 5, '101' encodes polynomial X^2 + 1 in a GF(2)[X], which factors as (X+1)(X+1), and thus is not irreducible in that ring (5 is not in A014580). From this follows that as those factors X+1 are encoded by 3 (11 in binary) that A234742(5) = 3*3 = 9 (instead of 5), and because 5 is a prime in N, it cannot be a product of any other numbers, from which we know that it doesn't occur at all in A234742.
a(6) = a(2*3) = 1 as a(2)*a(3) = 1.
PROG
(Scheme, with memoizing definec-macro from Antti Karttunen's IntSeq-library)
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Feb 03 2014
STATUS
approved