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

Author

Antti Karttunen, Dec 10 2015

Keywords

• nonn
• look

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000225, A001511, A002487, A003987, A010060, A011655, A048675, A055396, A125184, A248663, A260443, A265397, A277330.

Cf. A023758 (the fixed points).

Cf. also A068156, A168081, A265407.

Cf. A277700 (binary weight of terms).

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

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

Cf. also arrays A277710, A099884.

Programs

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

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

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

Other identities. For all n >= 0:

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)