Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #21 Mar 13 2014 14:28:38
%S 1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,0,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,
%T 0,0,1,1,1,1,0,1,1,0,1,0,0,1,1,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1,1,
%U 0,0,0,0,1,1,1,1,1,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,1,1,0,1,1,0,1,1,0,0
%N Characteristic function for A236842 (A234742): a(n) = 1, if n is a result of "upward" remultiplication (GF(2)[X] -> N) of some number, 0 otherwise.
%H Antti Karttunen, <a href="/A236862/b236862.txt">Table of n, a(n) for n = 0..8192</a>
%F 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.]
%F The same formula can be converted to a more standard notation with the help of De Morgan's laws:
%F 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))))).
%F a(n) = 1 iff A236853(n) > 0. [The latter sequence should also have a similar formula like above ones, only more complex.]
%e a(2)=1 because 2 is in A091206, so also in A014580, and A091225(2)=1.
%e a(3)=1 because 3 is in A091206, so also in A014580, and A091225(3)=1.
%e 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.
%e a(6) = a(2*3) = 1 as a(2)*a(3) = 1.
%e 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.
%o (Scheme, with memoizing definec-macro from _Antti Karttunen_'s IntSeq-library)
%o (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))))))))
%Y Cf. A236842, A234742, A014580, A091225, A236853, A236861, A235046.
%K nonn
%O 0
%A _Antti Karttunen_, Feb 03 2014