A268395 -id:A268395 - 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.

A268677 Complement of A268678; numbers that do not occur in A268395.

Original entry on oeis.org

2, 6, 9, 10, 12, 13, 14, 17, 21, 24, 25, 28, 29, 30, 33, 35, 38, 39, 43, 44, 45, 46, 49, 51, 54, 55, 58, 61, 62, 63, 67, 68, 71, 73, 76, 77, 78, 79, 80, 84, 85, 88, 91, 94, 95, 96, 97, 99, 100, 103, 107, 110, 111, 112, 114, 115, 118, 122, 125, 126, 128, 129, 130, 133, 137, 140, 141, 143, 144, 145, 146, 149, 152

Offset: 1

Antti Karttunen, Feb 10 2016

nonn

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

Cf. A268395, A268678.
Cf. A268712.
Cf. also A096346.

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

A268708 Number of iterations of A268395 needed to reach zero: a(0) = 0, for n >= 1, a(n) = 1 + a(A268395(n)).

Original entry on oeis.org

0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18

Offset: 0

Antti Karttunen, Feb 11 2016

nonn

Set k = n, take the k-th Xfactorial A048631(k) and find what is the maximum exponent h so that polynomial (X+1)^h still divides it (over GF(2), this can be computed with A268389, maybe also more directly). Set this h as a new value of k, and repeat. a(n) tells how many steps are needed before zero is reached.

Note that so far it is just an empirical observation that A268672(n) > 0 for all n > 0.

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

Cf. A048631, A268389, A268395, A268672.

Cf. also A268709, A268710.

a(0) = 0, for n >= 1, a(n) = 1 + a(A268395(n)).

A268672 a(n) = n - A268395(n).

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 2, 3, 4, 4, 3, 4, 4, 5, 6, 4, 5, 2, 2, 3, 2, 3, 4, 4, 4, 5, 6, 5, 6, 6, 4, 5, 6, 6, 3, 4, 4, 5, 6, 5, 4, 5, 6, 6, 7, 5, 5, 6, 6, 7, 8, 4, 5, 5, 4, 5, 6, 5, 5, 6, 4, 5, 6, 6, 7, 6, 6, 7, 4, 5, 6, 6, 6, 7, 8, 6, 7, 7, 6, 7, 6, 7, 8, 8, 9, 4, 4, 5, 6, 6, 4, 5, 5, 6, 7, 6, 6, 7, 8, 7, 8, 8, 4, 5, 6, 4, 4, 5, 4, 5, 6, 6, 7, 7, 6, 7, 7, 8, 9, 6, 4

Offset: 0

Antti Karttunen, Feb 10 2016

nonn

It seems that the sequence stays strictly positive after a(0).
Only 1 seems to be at a(1).
2's occur in this sequence at least in the following positions: 2, 3, 5, 6, 17, 18, 20, 257, 258, 260, 272, 65537, 65538, 65540, 65552, 65792, and in no other location up to 2^21.
See also comments in A268708.

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

Cf. A001317, A268395, A268708.

Cf. A268713 (record positions).

Scheme
```
(define (A268672 n) (- n (A268395 n)))
```

a(n) = n - A268395(n).

A268709 Number of iterations of A268395 needed to reach zero from 2^n: a(n) = A268708(2^n).

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 15, 25, 40, 75, 134, 246, 428, 802, 1453, 2643, 4587, 8851, 16849, 32368, 60503, 117343

Offset: 0

Antti Karttunen, Feb 11 2016

Cf. A000079, A268395, A268708, A268710.

(define (A268709 n) (A268708 (A000079 n)))

a(n) = A268708(2^n).

A268710 Number of iterations of A268395 needed to reach zero from 2^n + 1: a(n) = A268708(2^n + 1).

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 15, 25, 41, 75, 134, 246, 428, 802, 1454, 2643, 4588, 8851, 16849, 32368, 60504, 117343

Offset: 0

Antti Karttunen, Feb 11 2016

Cf. A000051, A268395, A268708, A268709.

(define (A268710 n) (A268708 (+ 1 (A000079 n))))

a(n) = A268708((2^n)+1).

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

A268677 Complement of A268678; numbers that do not occur in A268395.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A268708 Number of iterations of A268395 needed to reach zero: a(0) = 0, for n >= 1, a(n) = 1 + a(A268395(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A268672 a(n) = n - A268395(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A268709 Number of iterations of A268395 needed to reach zero from 2^n: a(n) = A268708(2^n).

Views

Author

Keywords

Crossrefs

Programs

Scheme

Formula

A268710 Number of iterations of A268395 needed to reach zero from 2^n + 1: a(n) = A268708(2^n + 1).

Views

Author

Keywords

Crossrefs

Programs

Scheme

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