0

Antti Karttunen, Table of n, a(n) for n = 0..8192

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.]

a(2)=1 because 2 is in A091206, so also in A014580, and A091225(2)=1.

a(3)=1 because 3 is in A091206, so also in A014580, and A091225(3)=1.

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.

a(25) = a(5*5) = 1, because, although a(5)=0, 25 itself is in A014580, thus A091225(25)=1, and a(25)=1 also.

(Scheme) ;; With memoizing definec-macro from Antti Karttunen's IntSeq-library.

(definec (A236862 n) (cond ((< n 2) 1) ((= 1 (A091225 n)) 1) ((prime? n) 0) (else (let loop ((d 2)) (cond ((= d n) 0) ((and (integer? (/ n d)) (not (zero? (* (A236862 d) (A236862 (/ n d)))))) 1) (else (loop (+ d 1))))))))

Cf. A236842, A234742, A014580, A091225, A236853, A236861, A235046.

Sequence in context: A344880 A379406 A167020 * A163812 A163818 A345009

Adjacent sequences: A236859 A236860 A236861 * A236863 A236864 A236865

Antti Karttunen, Feb 03 2014

approved