cp's OEIS Frontend

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

%I A264977 #55 Mar 12 2021 07:52:05
%S A264977 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,
%T A264977 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,
%U A264977 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
%N A264977 a(0) = 0, a(1) = 1, a(2*n) = 2*a(n), a(2*n+1) = a(n) XOR a(n+1).
%C A264977 a(n) is the n-th Stern polynomial (cf. A260443, A125184) evaluated at X = 2 over the field GF(2).
%C A264977 For n >= 1, a(n) gives the index of the row where n occurs in array A277710.
%H A264977 Antti Karttunen, <a href="/A264977/b264977.txt">Table of n, a(n) for n = 0..16384</a>
%F A264977 a(0) = 0, a(1) = 1, a(2*n) = 2*a(n), a(2*n+1) = a(n) XOR a(n+1).
%F A264977 a(n) = A248663(A260443(n)).
%F A264977 a(n) = A048675(A277330(n)). - _Antti Karttunen_, Oct 27 2016
%F A264977 Other identities. For all n >= 0:
%F A264977 a(n) = n - A265397(n).
%F A264977 From _Antti Karttunen_, Oct 28 2016: (Start)
%F A264977 A000035(a(n)) = A000035(n). [Preserves the parity of n.]
%F A264977 A010873(a(n)) = A010873(n). [a(n) mod 4 = n mod 4.]
%F A264977 A001511(a(n)) = A001511(n) = A055396(A277330(n)). [In general, the 2-adic valuation of n is preserved.]
%F A264977 A010060(a(n)) = A011655(n).
%F A264977 a(n) <= n.
%F A264977 For n >= 2, a((2^n)+1) = (2^n) - 3.
%F A264977 The following two identities are so far unproved:
%F A264977 For n >= 2, a(3*A000225(n)) = a(A068156(n)) = 5.
%F A264977 For n >= 2, a(A068156(n)-2) = A062709(n) = 2^n + 3.
%F A264977 (End)
%e A264977 In this example, binary numbers are given zero-padded to four bits.
%e A264977 a(2) = 2a(1) = 2 * 1 = 2.
%e A264977 a(3) = a(1) XOR a(2) = 1 XOR 2 = 0001 XOR 0010 = 0011 = 3.
%e A264977 a(4) = 2a(2) = 2 * 2 = 4.
%e A264977 a(5) = a(2) XOR a(3) = 2 XOR 3 = 0010 XOR 0011 = 0001 = 1.
%e A264977 a(6) = 2a(3) = 2 * 3 = 6.
%e A264977 a(7) = a(3) XOR a(4) = 3 XOR 4 = 0011 XOR 0100 = 0111 = 7.
%t A264977 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 *)
%o A264977 (Scheme, with memoization-macro definec)
%o A264977 (definec (A264977 n) (cond ((<= n 1) n) ((even? n) (* 2 (A264977 (/ n 2)))) (else (A003987bi (A264977 (/ (- n 1) 2)) (A264977 (/ (+ n 1) 2))))))
%o A264977 ;; Where A003987bi computes bitwise-XOR as in A003987.
%o A264977 (Python)
%o A264977 class Memoize:
%o A264977     def __init__(self, func):
%o A264977         self.func=func
%o A264977         self.cache={}
%o A264977     def __call__(self, arg):
%o A264977         if arg not in self.cache:
%o A264977             self.cache[arg] = self.func(arg)
%o A264977         return self.cache[arg]
%o A264977 @Memoize
%o A264977 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)
%o A264977 print([a(n) for n in range(51)]) # _Indranil Ghosh_, Jul 27 2017
%Y A264977 Cf. A000225, A001511, A002487, A003987, A010060, A011655, A048675, A055396, A125184, A248663, A260443, A265397, A277330.
%Y A264977 Cf. A023758 (the fixed points).
%Y A264977 Cf. also A068156, A168081, A265407.
%Y A264977 Cf. A277700 (binary weight of terms).
%Y A264977 Cf. A277701, A277712, A277713 (positions of 1's, 2's and 3's in this sequence).
%Y A264977 Cf. A277711 (position of the first occurrence of each n in this sequence).
%Y A264977 Cf. also arrays A277710, A099884.
%K A264977 nonn,look
%O A264977 0,3
%A A264977 _Antti Karttunen_, Dec 10 2015