A268679 -id:A268679 - cp's OEIS frontend

A268678 Distinct values in A268395; partial sums of A268679.

0, 1, 3, 4, 5, 7, 8, 11, 15, 16, 18, 19, 20, 22, 23, 26, 27, 31, 32, 34, 36, 37, 40, 41, 42, 47, 48, 50, 52, 53, 56, 57, 59, 60, 64, 65, 66, 69, 70, 72, 74, 75, 81, 82, 83, 86, 87, 89, 90, 92, 93, 98, 101, 102, 104, 105, 106, 108, 109, 113, 116, 117, 119, 120, 121, 123, 124, 127, 131, 132, 134, 135, 136, 138, 139, 142

Offset: 0

Antti Karttunen, Feb 10 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..32768

Cf. A001969, A268395, A268679.
Cf. A268677 (complement).
Cf. A268680 (least monotonic left inverse).
Cf. A268712.
Cf. also A004128.

f[n_] := Which[n == 1, 0, OddQ@ #, 0, EvenQ@ #, 1 + f[#/2]] &@ Fold[BitXor, n, Quotient[n, 2^Range[BitLength@ n - 1]]]; Union@ Accumulate@ Array[f, {150}] (* Michael De Vlieger, Feb 12 2016, after Jan Mangaldan at A006068 *)

a(0) = 0, for n >= 1, a(n) = A268679(n) + a(n-1).
a(n) = A268395(A001969(1+n)).
Other identities. For all n >= 0:
A268680(a(n)) = n.

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

Antti Karttunen, Feb 10 2016

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.

			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.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences operating on GF(2)[X]-polynomials

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.

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

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

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

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

A268680 Least monotonic left inverse of A268678.

Original entry on oeis.org

0, 1, 1, 2, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 14, 14, 15, 16, 16, 16, 16, 17, 18, 18, 19, 19, 20, 21, 21, 21, 22, 23, 24, 24, 24, 24, 24, 25, 26, 26, 27, 27, 28, 29, 29, 29, 30, 31, 31, 32, 33, 33, 33, 33, 34, 35, 36, 36, 36, 37, 38, 38, 39, 39, 40, 41, 41, 41, 41, 41, 41, 42, 43, 44

Offset: 0

Antti Karttunen, Feb 11 2016

nonn

a(n) = number of distinct nonzero values A268395 that occur in range [0 .. n].

Each n occurs A268679(n+1) times.

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

Cf. A268678, A268679, A268395.

Cf. also A268711.

Other identities. For all n >= 0:

a(A268678(n)) = n.

cp's OEIS Frontend

A268678 Distinct values in A268395; partial sums of A268679.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A268680 Least monotonic left inverse of A268678.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula