login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A268669 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). 9
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, 11, 2, 31, 32, 31, 2, 35, 28, 37, 38, 11, 8, 41, 42, 25, 44, 7, 26, 47, 16, 49, 50, 1, 52, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

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.

No terms of A001969 occur so all terms are odious (in A000069). Each odious number occurs an infinitely many times.

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..65537

Eric Weisstein's World of Mathematics, Rule 60

Index entries for sequences related to cellular automata

Index entries for sequences operating on GF(2)[X]-polynomials

FORMULA

If A006068(n) is odd, then a(n) = n, otherwise a(n) = a(A006068(n)/2).

Other identities and observations. For all n >= 1:

a(n) = A003188(A268670(n)).

A010060(a(n)) = 1. [All terms are odious.]

a(n) <= n.

More precisely, a(A000069(n)) = A000069(n) and a(A001969(n)) < A001969(n).

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:

A048724^A268389(n) (a(n)) = n. [Starting from k = a(n), and iterating map k -> A048724(k) exactly A268389(n) times yields n back.]

A048720(a(n),A048723(3,A268389(n))) = A048720(a(n),A001317(A268389(n))) = n.

EXAMPLE

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.

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.

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

MATHEMATICA

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 *)

PROG

(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

(Scheme)

;; This employs the given recurrence and uses memoization-macro definec:

(definec (A268669 n) (if (odd? (A006068 n)) n (A268669 (/ (A006068 n) 2))))

(define (A268669 n) (let loop ((n n)) (let ((k (A006068 n))) (if (odd? k) n (loop (/ k 2)))))) ;; Computed in a loop, no memoization.

CROSSREFS

Cf. A001317 (positions of ones).

Cf. A000069, A001969, A003188, A003987, A010060, A048720, A048723, A048724, A268384, A268670.

Cf. A268389 (the highest exponent for (X+1)).

Cf. also A136386.

Sequence in context: A163618 A275392 A106616 * A030652 A224065 A077904

Adjacent sequences:  A268666 A268667 A268668 * A268670 A268671 A268672

KEYWORD

nonn,base

AUTHOR

Antti Karttunen, Feb 10 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 07:48 EDT 2019. Contains 328315 sequences. (Running on oeis4.)