|
| |
|
|
A236862
|
|
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.
|
|
6
|
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0
|
|
|
LINKS
|
|
|
|
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.
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.
|
|
|
PROG
|
(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))))))))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
