OFFSET
0,3
COMMENTS
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).
Other identities. For all n >= 0:
a(n) = n - A265397(n).
From Antti Karttunen, Oct 28 2016: (Start)
A001511(a(n)) = A001511(n) = A055396(A277330(n)). [In general, the 2-adic valuation of n is preserved.]
a(n) <= n.
For n >= 2, a((2^n)+1) = (2^n) - 3.
The following two identities are so far unproved:
(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
KEYWORD
nonn,look
AUTHOR
Antti Karttunen, Dec 10 2015
STATUS
approved