cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A268671 a(n) = (A268670(n)+1) / 2.

Original entry on oeis.org

1, 2, 1, 4, 1, 2, 3, 8, 3, 2, 7, 4, 5, 6, 1, 16, 1, 6, 15, 4, 13, 14, 5, 8, 9, 10, 3, 12, 7, 2, 11, 32, 11, 2, 31, 12, 29, 30, 7, 8, 25, 26, 9, 28, 3, 10, 27, 16, 17, 18, 1, 20, 15, 6, 19, 24, 5, 14, 23, 4, 21, 22, 13, 64, 13, 22, 63, 4, 61, 62, 21, 24, 57, 58, 5, 60, 23, 14, 59, 16, 49, 50, 17, 52, 1
Offset: 1

Views

Author

Antti Karttunen, Feb 10 2016

Keywords

Links

Crossrefs

Cf. A001317 (positions of ones).
Cf. A268669, A268670.

Programs

  • Mathematica
    f[n_] := Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; g[n_] := If[OddQ@ #, n, g[#/2]] &@ f[n]; Table[(f@ g@ n + 1)/2, {n, 85}]  (* Michael De Vlieger, Feb 12 2016, after Jan Mangaldan at A006068 *)
  • Scheme
    (define (A268671 n) (/ (+ 1 (A268670 n)) 2))

Formula

a(n) = (A268670(n)+1) / 2.

A268389 a(n) = greatest k such that polynomial (X+1)^k divides the polynomial (in polynomial ring GF(2)[X]) that is encoded in the binary expansion of n. (See the comments for details).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 0, 3, 0, 4, 1, 0, 2, 0, 0, 1, 1, 0, 0, 2, 0, 1, 3, 0, 0, 1, 4, 0, 1, 0, 0, 2, 2, 0, 0, 1, 0, 3, 1, 0, 1, 0, 0, 5, 0, 1, 2, 0, 0, 2, 1, 0, 3, 0, 0, 1, 0, 2, 1, 0, 4, 0, 0, 1, 1, 0, 0, 3, 0, 1, 2, 0, 2, 0, 0, 1, 0, 6, 1, 0, 0, 1, 3, 0, 1, 0, 0, 2, 1, 0, 0, 2, 0, 1, 5, 0, 0, 3, 1, 0, 2, 0, 0, 1, 0, 1, 2, 0, 1, 0, 0, 4, 3
Offset: 1

Views

Author

Antti Karttunen, Feb 10 2016

Keywords

Comments

a(n) gives the number of iterations of map k -> A006068(k)/2 that are required (when starting from k = n) until k is an odd number.
A001317 gives the record positions and particularly, A001317(n) gives the first occurrence of n in this sequence.
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) = the number of times polynomial X+1 (encoded by 3, "11" in binary) divides the polynomial encoded by n.

Examples

			For n = 5 ("101" in binary) which encodes polynomial x^2 + 1, we see that it can be factored over GF(2) as (X+1)(X+1), and thus a(5) = 2.
For n = 8 ("1000" in binary) which encodes polynomial x^3, we see that it is not divisible in ring GF(2)[X] by polynomial X+1, thus a(8) = 0.
For n = 9 ("1001" in binary) which encodes polynomial x^3 + 1, we see that it can be factored over GF(2) as (X+1)(X^2 + X + 1), and thus a(9) = 1.

Links

Crossrefs

Cf. A001317, A006068, A007949, A048720, A048723, A048724, A057889, A268384, A235042, A268670.
Cf. A268669 (quotient left after (X+1)^a(n) has been divided out).
Cf. A268395 (partial sums).
Cf. A000069 (positions of zeros), A268679 (this sequence without zeros).
Cf. also A037096, A037097, A136386.

Programs

  • Mathematica
    f[n_] := Which[n == 1, 0, OddQ@ #, 0, EvenQ@ #, 1 + f[#/2]] &@ Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; Array[f, {120}] (* Michael De Vlieger, Feb 12 2016, after Jan Mangaldan at A006068 *)
  • PARI
    a(n) = {my(b = binary(n), p = Pol(binary(n))*Mod(1,2), k = poldegree(p)); while (type(p/(x+1)^k*Mod(1,2)) != "t_POL", k--); k;} \\ Michel Marcus, Feb 12 2016
  • Scheme
    ;; This employs the given recurrence and uses memoization-macro definec:
(definec (A268389 n) (if (odd? (A006068 n)) 0 (+ 1 (A268389 (/ (A006068 n) 2)))))
(define (A268389 n) (let loop ((n n) (s 0)) (let ((k (A006068 n))) (if (odd? k) s (loop (/ k 2) (+ 1 s)))))) ;; Computed in a loop, no memoization.

Formula

If A006068(n) is odd, then a(n) = 0, otherwise a(n) = 1 + a(A006068(n)/2).
Other identities. For all n >= 0:
a(A001317(n)) = n. [The sequence works as a left inverse of A001317.]
A048720(A268669(n),A048723(3,a(n))) = A048720(A268669(n),A001317(a(n))) = n.
A048724^a(n) (A268669(n)) = n. [The a(n)-th fold application (power) of A048724 when applied to A268669(n) gives n back.]
a(n) = A007949(A235042(n)).
a(A057889(n)) = a(n).

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

Original entry on oeis.org

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
Offset: 1

Views

Author

Antti Karttunen, Feb 10 2016

Keywords

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.

Examples

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

Links

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.

Programs

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

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.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.