|
%I #48 Feb 13 2016 23:16:04
%S 1,2,1,4,1,2,7,8,7,2,11,4,13,14,1,16,1,14,19,4,21,22,13,8,25,26,7,28,
%T 11,2,31,32,31,2,35,28,37,38,11,8,41,42,25,44,7,26,47,16,49,50,1,52,
%U 19,14,55,56,13,22,59,4,61,62,21,64,21,62,67,4,69,70,61,56,73,74,13,76,59,22,79,16,81,82,49,84,1
%N a(n) = polynomial quotient (computed over GF(2), result is its binary encoding) that is left after all instances of polynomial (X+1) have been factored out of the polynomial that is encoded by the binary expansion of n. (See comments for details).
%C When polynomials over GF(2) are encoded in the binary representation of n in a natural way where each polynomial b(n)*X^n+...+b(0)*X^0 over GF(2) is represented by the binary number b(n)*2^n+...+b(0)*2^0 in N (each coefficient b(k) is either 0 or 1), then a(n) = representation of the polynomial that is left as a quotient when all X+1 polynomials (encoded by 3, "11" in binary) have been divided out.
%C Each a(n) is one of the "Garden of Eden" patterns of Rule-60 one-dimensional cellular automaton, a seed pattern which after A268389(n) generations yields the configuration encoded in binary expansion of n.
%C No terms of A001969 occur so all terms are odious (in A000069). Each odious number occurs an infinitely many times.
%H Antti Karttunen, <a href="/A268669/b268669.txt">Table of n, a(n) for n = 1..65537</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rule60.html">Rule 60</a>
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%H <a href="/index/Ge#GF2X">Index entries for sequences operating on GF(2)[X]-polynomials</a>
%F If A006068(n) is odd, then a(n) = n, otherwise a(n) = a(A006068(n)/2).
%F Other identities and observations. For all n >= 1:
%F a(n) = A003188(A268670(n)).
%F A010060(a(n)) = 1. [All terms are odious.]
%F a(n) <= n.
%F More precisely, a(A000069(n)) = A000069(n) and a(A001969(n)) < A001969(n).
%F The equivalence of the following two formulas stems from the additive nature of Rule-60 cellular automaton. Or more plainly, because carryless binary multiplication A048720 distributes over carryless binary sum, XOR A003987:
%F A048724^A268389(n) (a(n)) = n. [Starting from k = a(n), and iterating map k -> A048724(k) exactly A268389(n) times yields n back.]
%F A048720(a(n),A048723(3,A268389(n))) = A048720(a(n),A001317(A268389(n))) = n.
%e For n = 5 ("101" in binary) which encodes polynomial x^2 + 1, we observe that it can be factored in ring GF(2)[X] as (X+1)(X+1), and thus a(5) = 1, because after dividing both instances of (X+1) off, we are left with the quotient polynomial 1 which is encoded by 1.
%e For n = 8 ("1000" in binary) which encodes polynomial x^3, we observe that it is not divisible in ring GF(2)[X] by polynomial X+1, thus a(8) = 8.
%e For n = 9 ("1001" in binary) which encodes polynomial x^3 + 1, we observe that it can be factored over GF(2) as (X+1)(X^2 + X + 1), and thus a(9) = 7, because the quotient polynomial X^2 + X + 1 is encoded by 7 ("111" in binary).
%t f[n_] := If[OddQ@ #, n, f[#/2]] &@ Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; Array[f, {85}] (* _Michael De Vlieger_, Feb 12 2016, after _Jan Mangaldan_ at A006068 *)
%o (PARI) a(n) = {p = Pol(binary(n))*Mod(1,2); q = (x+1)*Mod(1,2); while (type(r = p/q) == "t_POL", p = r); np = Polrev(vector(poldegree(p)+1, k, k--; lift(polcoeff(p, k)))); subst(np, x, 2);} \\ _Michel Marcus_, Feb 12 2016
%o (Scheme)
%o ;; This employs the given recurrence and uses memoization-macro definec:
%o (definec (A268669 n) (if (odd? (A006068 n)) n (A268669 (/ (A006068 n) 2))))
%o (define (A268669 n) (let loop ((n n)) (let ((k (A006068 n))) (if (odd? k) n (loop (/ k 2)))))) ;; Computed in a loop, no memoization.
%Y Cf. A001317 (positions of ones).
%Y Cf. A000069, A001969, A003188, A003987, A010060, A048720, A048723, A048724, A268384, A268670.
%Y Cf. A268389 (the highest exponent for (X+1)).
%Y Cf. also A136386.
%K nonn,base
%O 1,2
%A _Antti Karttunen_, Feb 10 2016
|
