A264977 a(0) = 0, a(1) = 1, a(2*n) = 2*a(n), a(2*n+1) = a(n) XOR a(n+1).

0, 1, 2, 3, 4, 1, 6, 7, 8, 5, 2, 7, 12, 1, 14, 15, 16, 13, 10, 7, 4, 5, 14, 11, 24, 13, 2, 15, 28, 1, 30, 31, 32, 29, 26, 7, 20, 13, 14, 3, 8, 1, 10, 11, 28, 5, 22, 19, 48, 21, 26, 15, 4, 13, 30, 19, 56, 29, 2, 31, 60, 1, 62, 63, 64, 61, 58, 7, 52, 29, 14, 19, 40, 25, 26, 3, 28, 13, 6, 11, 16, 9, 2, 11, 20, 1, 22

Offset

0,3

Comments

a(n) is the n-th Stern polynomial (cf. A260443, A125184) evaluated at X = 2 over the field GF(2).

For n >= 1, a(n) gives the index of the row where n occurs in array A277710.

Links

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

Formula

a(0) = 0, a(1) = 1, a(2*n) = 2*a(n), a(2*n+1) = a(n) XOR a(n+1).

a(n) = A248663(A260443(n)).

a(n) = A048675(A277330(n)). - Antti Karttunen, Oct 27 2016

a(n) = n - A265397(n).

From Antti Karttunen, Oct 28 2016: (Start)

A000035(a(n)) = A000035(n). [Preserves the parity of n.]

A010873(a(n)) = A010873(n). [a(n) mod 4 = n mod 4.]

A001511(a(n)) = A001511(n) = A055396(A277330(n)). [In general, the 2-adic valuation of n is preserved.]

A010060(a(n)) = A011655(n).

a(n) <= n.

For n >= 2, a((2^n)+1) = (2^n) - 3.

The following two identities are so far unproved:

For n >= 2, a(3*A000225(n)) = a(A068156(n)) = 5.

For n >= 2, a(A068156(n)-2) = A062709(n) = 2^n + 3.

(End)

Example

In this example, binary numbers are given zero-padded to four bits.
a(2) = 2a(1) = 2 * 1 = 2.
a(3) = a(1) XOR a(2) = 1 XOR 2 = 0001 XOR 0010 = 0011 = 3.
a(4) = 2a(2) = 2 * 2 = 4.
a(5) = a(2) XOR a(3) = 2 XOR 3 = 0010 XOR 0011 = 0001 = 1.
a(6) = 2a(3) = 2 * 3 = 6.
a(7) = a(3) XOR a(4) = 3 XOR 4 = 0011 XOR 0100 = 0111 = 7.

Mathematica

recurXOR[0] = 0; recurXOR[1] = 1; recurXOR[n_] := recurXOR[n] = If[EvenQ[n], 2recurXOR[n/2], BitXor[recurXOR[(n - 1)/2 + 1], recurXOR[(n - 1)/2]]]; Table[recurXOR[n], {n, 0, 100}] (* Jean-François Alcover, Oct 23 2016 *)

Prog

(Scheme) ;; With memoization-macro definec.
(definec (A264977 n) (cond ((<= n 1) n) ((even? n) (* 2 (A264977 (/ n 2)))) (else (A003987bi (A264977 (/ (- n 1) 2)) (A264977 (/ (+ n 1) 2))))))
;; Where A003987bi computes bitwise-XOR as in A003987.
(Python)
class Memoize:
    def __init__(self, func):
        self.func=func
        self.cache={}
    def __call__(self, arg):
        if arg not in self.cache:
            self.cache[arg] = self.func(arg)
        return self.cache[arg]
@Memoize
def a(n): return n if n<2 else 2*a(n//2) if n%2==0 else a((n - 1)//2)^a((n + 1)//2)
print([a(n) for n in range(51)]) # Indranil Ghosh, Jul 27 2017

Crossrefs

Cf. A000225, A001511, A002487, A003987, A010060, A011655, A048675, A055396, A125184, A248663, A260443, A265397, A277330, A283975 (odd bisection).

Cf. A023758 (the fixed points).

Cf. also A068156, A168081, A265407

Cf. A277700 (binary weight of terms).

Cf. A277701, A277712, A277713, A277715 (positions of 1's, 2's, 3's and 5's in this sequence).

Cf. A277711 (position of the first occurrence of n in this sequence).

Cf. A277815, A277816 (the least k > n for which a(k) = a(n)), A277817, A277826 [the least k for which a(k) = a(n)], and permutation A277695.

Cf. also arrays A277710, A099884.

Cf. A283979 [= (n XOR a(n))/4], compare also the scatter plots.

Sequence in context: A049073 A076388 A354988 * A109680 A366373 A277826

Adjacent sequences: A264974 A264975 A264976 * A264978 A264979 A264980

Keyword

nonn,look

Author

Antti Karttunen, Dec 10 2015

Status

approved